Java 二分查找与优化思路

二分查找是一种高效的查找方法。其主要思路是：对已经排序的数据，每次取二分之一处的元素与目标元素比较，如果相等就返回目标位置，否则继续下一轮查找。

二分思想

二分查找文字描述：

1. 排好序的数组 arr
2. 定义左边界 left、右边界 right，循环二分
3. 取中间索引 mid = (left + right) / 2
4. 中间索引值 arr[mid] 与目标值 target 比较
   4.1 arr[mid] = target 表示找到目标，返回中间索引 mid
   4.2 arr[mid] > target 目标位于左区间，将右边界设为 mid – 1，下一轮查找
   4.2 arr[mid] < target 目标位于右区间，将左边界设为 mid + 1，下一轮查找
5. left > right 时，表示目标元素不在数组中，返回 -1

经典实现

为了方便测试，下面定义了一个二分查找的基本结构：

public static void main(String[] args) {
    int[] nums = {1,3,4,5,7,9};
    int target = 3;
    int idx = binarySearch(nums, target);
    System.out.println(idx);
}

private static int binarySearch(int[] arr, int target) {

    return -1;
}

二分查找的核心代码如下：

private static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(arr[mid] > target){
            right = mid - 1;
        }else if(arr[mid] < target){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

其中有两个注意的点：

• right 初始值为数组长度 -1
• while 循环中需要考虑 left = right 的情况

整数溢出问题

当数据量不大时，上面的方法没有任何问题，当数组中的元素很多时，可能存在如下的场景：

public static void overflow(){
    // 初始左边界为 0
    int left = 0;
    // 初始右边界为数组长度 - 1 ，假设数组中有 Integer.MAX_VALUE 个元素
    int right = Integer.MAX_VALUE - 1;

    // 第一轮查找
    int mid = (left + right) / 2;
    System.out.println("第一轮查找，中间值" + mid);
    // 如果此时 target 位于数组右半边
    left = mid + 1;

    // 第二轮查找
    mid = (left + right) / 2;

    System.out.println("第二轮查找，中间值" + mid);
}

当第二轮查找时，数据发生了溢出，中间值变成了负数，这样就可能导致返回值和预期不符。

数学变换

为此，我们需要对中间值的计算过程做一定的变换：

(left + right) / 2
->
left / 2 + right / 2
->
left - left / 2 + right / 2
->
left - (left - right) / 2
->
left + (right - left) / 2

使用变换后的公式，在检验一下：

public static void overflow(){
    int left = 0;
    int right = Integer.MAX_VALUE - 1;

    // 第一轮查找
    int mid = left + (right - left) / 2;
    System.out.println("第一轮查找，中间值" + mid);
    // 如果此时 target 位于数组右半边
    left = mid + 1;

    // 第二轮查找
    mid = left + (right - left) / 2;

    System.out.println("第二轮查找，中间值" + mid);
}

这样就不存在整数溢出问题了。

位运算

对于正整数，除以二相当于无符号右移一位。基于这一特点，我们可以使用位运算解决溢出问题：

public static void overflow(){
    int left = 0;
    int right = Integer.MAX_VALUE - 1;

    // 第一轮查找
    int mid = (left + right) >>> 1;
    System.out.println("第一轮查找，中间值" + mid);
    // 如果此时 target 位于数组右半边
    left = mid + 1;

    // 第二轮查找
    mid = (left + right) >>> 1;

    System.out.println("第二轮查找，中间值" + mid);
}

对于计算机，右移比除法的效率要高，这也是推荐的一种方式。

完整的二分查找代码：

public class Binary {

    public static void main(String[] args) {
        int[] nums = {1,3,4,5,7,9};
        int target = 3;
        int idx = binarySearch(nums, target);
        System.out.println(idx);
    }

    private static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(arr[mid] > target){
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}