二分查找模板详解

二分查找

二分查找主要是用于来一个有序区间内找到符合条件的数，每一次都选择中间的数进行判断然后将搜索空间减半。

举个例子，我们需要在1-8内搜索数字2，那么首先假设左面边界为1，右面边界为8，然后找到中间的元素和我们的目标元素作比较

中间元素4>3，这个时候需要将右边界移动到mid-1的位置

这样就将原来的搜索空间减半，只需要在1-3这个区间内进行搜索即可，再次搜索之后就能够查找到元素2。
需要注意的是，上面二分查找主要分为下面几个步骤：

1. 确定左右边界
2. 确定中间元素
3. 判断目标元素与中间元素关系，缩小搜索空间

我们分别对这几个部分进行详细介绍：

1 确定左右边界

根据题目的条件选择目标可能存在的范围，注意这个范围一定要选择准确否则便不一定能搜索到目标值，一般搜索对象是数组中的值，这个时候搜索的左右指针对应数组的左右边界，该边界从0开始一直到size-1。如果确定目标值就在这个边界内，那么最后返回的结果就是left或者right(两者指向相同)，如果目标值不一定在这个边界内，还需要在退出循环的时候进行一次判断。

2 确定中间元素

在传统的二分查找模板中一般会使用mid=(left+right)/2 作为中间元素，但是这样可能会存在整型变量的越界，为了避免越界一般会使用mid=left+(right-left)/2 或者是mid = (left+ right) >>> 1
（无符号右移一位）这种写法，当然你可能还看到过mid=(left+right+1)/2 或者mid=left+(right-left+1)/2 或者mid = (left+ right+1) >>> 1 这种写法，两种写法有什么区别呢？在待搜索区间的个数为奇数的时候两种写法得到的中间指针是一样的，当区间个数为偶数的时候第一种写法得到的是左中位数，第二种写法得到的是右中位数，如下面的图所示：

那么在实际应用过程该选用左中位数还是右中位数作为mid值呢？这实际与我们下面的缩小搜索区间的操作有关。为了便于理解，我们在下面的分析中采用(left+right)/2或者(left+right+1)/2这种形式作为区间中点。代码中使用(left+right)>>>1的写法

3 判断目标元素与中间元素关系，缩小搜索空间

当确定中间元素之后我们就需要将其与目标元素进行比较，此时我们能够确定的是某一个区间内一定不会含有目标元素。我们需要将对应的这一个区间去掉即可。在去掉对应区间的时候一定要注意区间的端点是不是可能为目标值，如果其可能为目标值就要保留这个端点，反之就要舍弃。

例如我们想要查找大于2.5的第一个元素的时候，第一次找到中间元素为3，那么从mid到right之间的元素一定都要比目标大，而我们需要找到大于其的第一个元素，所以mid后面的元素都不可能为最终结果，而端点值mid=3有可能为目标值所以需要保留，此时区间的选择应该是right=mid

进一步的，再次计算区间中点并与目标值作比较，此时的mid=2一定不是目标值(我们要找大于2.5的第一个数)，所以在缩小区间的时候mid值就不需要考虑在内

此时缩小区间left=mid+1

一般的，在二分查找中我们的循环条件就是left<right为true的时候，此时显然已经相等，退出循环后目标的值就等于left或者right所指向的值。一个对应的java程序如下：

public int searchNum(int[] nums, int target){
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        while (left < right){
            int mid = (left + right)>>>1;
            if ( nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return nums[ left ];
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在上面的例题中有一个很重要的点在于当我们缩小区间的时候保留了右区间的端点值(right=mid)而不考虑左区间的端点值(left=mid+1)，在这种情况下我们选择的区间中点是mid=(left+right)/2，注意这并不是随机选取的，我们可以首先说明一下这个规则：

• 当右区间端点可能为目标值的时候，我们选取中位数的时候就需要选取左中位数

  也就是right=mid的时候对应着mid=(left+right)/2

• 当左区间端点可能为目标值的时候，我们选取中位数的时候就需要选取右中位数

  也就是right=mid的时候对应着mid=(left+right+1)/2

如果不遵循这个规则的话就有可能会陷入死循环中，例如上面的题中假设我们的区间为1-6同样找大于5的第一个整数，选取区间中点的方式是mid=(left+right+1)/2，那么就有下面陷入循环的情况发生

我们在上面提到过区间中点的选择和缩小区间的操作有关其实就是指的上面的两条规则，我们将两条规则对应的代码模板总结如下，在实际应用中根据具体问题选择两个模板中的任意一个：

int left = 0;
int right = end;

1.右区间端点可能包含目标值的时候
while (left < right){
    int mid = (left + right)>>>1;//中点选择左中位数
    if ( nums[mid] < target){
        left = mid + 1;
    }else {
        right = mid;
    }
}

2.左区间端点可能包含目标值的时候
while (left < right){
    int mid = (left + right + 1)>>>1;//中点选择右中位数
    if ( nums[mid] > target){
        right = mid - 1;
    }else {
        left = mid;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

参考链接：
十分好用的二分查找法模板（Python 代码、Java 代码）