Java程序员看过来！手把手教你搞定二分查找算法

还在为二分查找算法发愁吗？这篇“Java程序员必看！手把手教你实现二分查找算法”文章，将带你彻底掌握这一高效查找利器！二分查找，又称折半查找，凭借其每次排除一半查找范围的特性，在有序数据中快速定位目标值。文章详细讲解了二分查找的两种实现方式：循环和递归，并提供清晰的Java示例代码，助你轻松理解。此外，还深入探讨了二分查找的常见变体及应用场景，如查找第一个大于等于或最后一个小于等于目标值的元素，以及在有序数组查找、数值逼近、数据库索引等方面的应用。更重要的是，文章分享了实用的调试技巧，助你避开常见的边界条件陷阱，编写出高效稳定的二分查找代码。

二分查找是一种高效的查找算法，其核心在于每次比较都排除一半的查找范围，从而快速定位目标值，但要求数据必须有序。实现方式有两种：1. 循环实现通过 while(left <= right) 不断调整 left 和 right 的值，计算 mid = left + (right - left)/2 防止溢出；2. 递归实现通过自身调用并传入新的 left 和 right 值缩小查找范围。时间复杂度为 O(log n)，常见变体包括查找第一个大于等于或最后一个小于等于目标值的元素，需细致处理边界条件。应用场景涵盖有序数组查找、特定范围查找、数值逼近、游戏决策及数据库索引等。调试时应检查循环条件、手动模拟、使用断言和编写充分单元测试以减少错误。

二分查找，也叫折半查找，是一种高效的查找算法。它的核心在于每次比较都排除掉一半的查找范围，从而快速定位目标值。关键在于数据必须是有序的。

二分查找的Java实现，就是利用循环或者递归，不断缩小搜索范围，直到找到目标值或者确定目标值不存在。

解决方案

二分查找的实现方式有两种：循环和递归。这里分别给出示例代码。

1. 循环实现

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止 (left + right) 溢出
            if (arr[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (arr[mid] < target) {
                left = mid + 1; // 目标值在右半部分，更新左边界
            } else {
                right = mid - 1; // 目标值在左半部分，更新右边界
            }
        }

        return -1; // 没有找到目标值，返回 -1
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 8, 11, 12};
        int target = 13;
        int index = binarySearch(arr, target);

        if (index == -1) {
            System.out.println("Element is not found!");
        } else {
            System.out.println("Element is found at index: " + index);
        }
    }
}

这段代码的核心是 while (left <= right) 循环。每次循环都计算中间位置 mid，然后根据 arr[mid] 与 target 的大小关系，调整 left 或 right 的值。mid = left + (right - left) / 2; 这种写法可以有效防止 (left + right) 溢出。

2. 递归实现

public class BinarySearchRecursive {

    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 没有找到目标值
        }

        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分递归查找
        } else {
            return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分递归查找
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 8, 11, 12};
        int target = 13;
        int index = binarySearchRecursive(arr, target, 0, arr.length - 1);

        if (index == -1) {
            System.out.println("Element is not found!");
        } else {
            System.out.println("Element is found at index: " + index);
        }
    }
}

递归实现的核心在于 binarySearchRecursive 方法的自身调用。每次调用都传入新的 left 和 right 值，缩小查找范围。

二分查找的时间复杂度是 O(log n)，非常高效。但前提是数组必须是有序的。如果数组无序，需要先排序，排序的时间复杂度通常是 O(n log n)。

二分查找有哪些常见的变体？

二分查找的变体主要体现在对边界条件的处理上。比如，查找第一个大于等于目标值的元素、查找最后一个小于等于目标值的元素等等。这些变体都需要对循环条件和边界条件进行细致的调整。

以查找第一个大于等于目标值的元素为例，代码如下：

public static int binarySearchFirstGreaterOrEqual(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int index = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            index = mid;
            right = mid - 1; // 继续在左半部分查找
        } else {
            left = mid + 1; // 在右半部分查找
        }
    }

    return index;
}

关键在于 arr[mid] >= target 时，不仅要记录 mid，还要继续在左半部分查找，直到找到第一个大于等于目标值的元素。

二分查找在实际应用中有哪些场景？

二分查找广泛应用于各种需要快速查找的场景，比如：

• 有序数组查找： 这是最直接的应用。
• 在排序数组中查找特定范围的元素： 可以结合二分查找的变体实现。
• 数值逼近： 比如求一个数的平方根，可以通过二分查找不断逼近。
• 在某些游戏或算法中进行决策： 比如猜数字游戏，或者在一些搜索算法中进行剪枝。

另外，数据库索引的实现也经常用到二分查找的思想。

二分查找的边界条件容易出错，有什么好的调试技巧？

二分查找的边界条件确实容易出错。调试时，可以采用以下技巧：

1. 仔细检查循环条件： 确保循环条件 left <= right 或 left < right 的使用正确。
2. 手动模拟： 选取一些典型的测试用例，手动模拟二分查找的过程，观察 left、right 和 mid 的变化。
3. 使用断言： 在代码中加入断言，检查 left、right 和 mid 的值是否符合预期。例如，可以断言 left 始终小于等于 right。
4. 编写单元测试： 编写充分的单元测试，覆盖各种边界情况，比如空数组、只有一个元素的数组、目标值在数组的开头或结尾等等。

例如，可以添加如下断言：

assert left <= right : "Left should be less than or equal to right";

通过这些调试技巧，可以有效地减少二分查找的错误。

终于介绍完啦！小伙伴们，这篇关于《Java程序员看过来！手把手教你搞定二分查找算法》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！