Java中如何实现二分查找 掌握二分查找的算法实现

二分查找是一种高效的查找算法，其核心在于每次比较都排除一半的查找范围，从而快速定位目标值，但要求数据必须有序。实现方式有两种：1. 循环实现通过 while(left

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

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

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

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

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