二分查找算法详解：从基础到优化

二分查找算法详解：从基础到优化

引用

CSDN

1.

https://blog.csdn.net/Broken_x/article/details/141929248

什么是二分查找？

二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。其基本思想是通过逐步缩小查找范围，每次将查找区间减半，从而大大提高查找效率。二分查找的时间复杂度为O(log n)，远优于线性查找的O(n)。

使用二分查找的前提条件是，数组是有序的。

基本实现代码

public static int binarySearchbasic(int[] arr, int target) {
    int i = 0, j = arr.length - 1; // 设置两个指针
    while (i <= j) { // 当左右指针没有重合时
        int m = (i + j) / 2; // 计算中间位置，Java语言的整数除法自动向下取整
        if (arr[m] == target) { // 如果找到目标值，返回位置
            return m;
        } else if (arr[m] > target) { // 目标值在左半部分
            j = m - 1;
        } else { // 目标值在右半部分
            i = m + 1;
        }
    }
    return -1; // 如果没有找到目标值，返回-1
}

代码执行步骤：
m 代表中间元素，如果目标值小于中间元素，那么直接将j =m-1，找左半部分，反之就找右半部分，如果目标值=中间元素，那么直接找到了，返回索引。如果不符合这三种情况，说明该数组里没有这个元素，直接返回-1.表示没有找到。

这应该很容易理解，也能大幅提升查找效率。

问题思考

1. 为什么是i<=j而不是i<j？
   
   因为i和j是指针，指向数组的第一个元素和最后一个元素，如果要查找的元素刚好是第一个或者最后一个元素 ，当i和j重合时，说明数组中没有目标值，返回-1，这样会导致结果不符，所以要采用<=。

2. (i+j)/2 有没有问题？
   考虑到可能会int溢出，如果两个数过大，采用除2 就有可能导致出现负数，而且Java语言的int类型是自动向下取整的，有些其他语言是需要你自己做取整的，比如 （0+7）/2 等于 3.5，我们都知道没有3.5这个索引，所以需要取整，改用 (i+j)>>>1,右移一位相当于除以2，效率更高，假如换成其他语言也可以写成右移1位，这样就不需要考虑取整问题，泛用性更好。

改进代码

这也是为什么有些大佬的二分查找代码和这个不一样的原因，我们需要再改进一下代码

public static int binarySearchAdvanced(int[] arr, int target) {
    int i = 0, j = arr.length; // 将j初始化为数组的长度，这样可以避免数组越界
    while (i < j) { // 改成< ，因为i和j是指针，指向数组的第一个元素和最后一个元素，当i和j重合时，说明数组中没有目标值，返回-1。
        int m = (i + j) >>> 1;
        if (arr[m] == target)
            return m;
        else if (arr[m] > target)
            j = m; // 改成j = m，因为m可能是第一个元素，此时i=0，j=m，i<j，所以不会进入循环。
        else
            i = m + 1;
    }
    return -1;
}

改版2号

// 二分查找平衡版
public static int binarySearchBalanced(int[] arr, int target) {
    int i = 0, j = arr.length;
    while (1 < j - i) {
        int m = (i + j) >>> 1;
        if (target < arr[m])
            j = m;
        else
            i = m;
    }
    if (i < arr.length && arr[i] == target)
        return i;
    else
        return -1;
}

改进的优点：

1. 避免数组越界：将j初始化为arr.length，避免了在计算中间位置时可能出现的数组越界问题。
2. 整数溢出预防：使用(i + j) >>> 1替代(i + j) / 2，有效防止了整数溢出问题。
3. 逻辑简化：通过调整循环条件和指针移动方式，简化了代码逻辑，使其更易于理解和维护。
4. 将j初始化为数组的长度，这样可以避免数组越界
5. 改成< ，因为i和j是指针，指向数组的第一个元素和最后一个元素，当i和j重合时，说明数组中没有目标值，返回-1。

**原来是j = m -1,改成j = m，因为m可能是第一个元素，此时i=0，j=m，i<j，所以不会进入循环。**

测试

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    System.out.println(binarySearchbasic(arr, 5)); // 输出: 4
    System.out.println(binarySearchbasic(arr, 11)); // 输出: -1
    System.out.println(binarySearchAdvanced(arr, 5)); // 输出: 4
    System.out.println(binarySearchAdvanced(arr, 11)); // 输出: -1
}

通过以上示例，可以看到二分查找算法的高效性和实用性。改进后的实现不仅提高了代码的健壮性，还增强了其可读性和维护性。