二分查找算法概述

二分查找很简单吗？或许二分查找的思想是直观的，但是细节才是程序的核心。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

二分代码的框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums,int target){
    int left = 0;
    int right = ...; // 一般是数组的长度
    while(...){
        int mid = (left + right) / 2;           //普通写法
        //int mid = left + (right - left) / 2;    // 防止溢出
        if(nums[mid] == target){
            ...
        }else if(nums[mid] < target){
            left = ...
        }else if(nums[mid] > target){
            right = ...
        }
    }
    return ...; // 没有找到  
}

这里虽然可以用else来简化代码，但是为了更好的理解二分查找的逻辑，这里还是用了if-else的写法。这样可以保留更多的二分比较的细节，作为初学者来说更易理解。

其中**…**标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。

另外声明一下，计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2，可以暂时先不管这个问题，后文会详细解释。

二分查找一个数

二分查找的最基础应用，即给定一个有序数组，查找某个数是否存在，如果存在则返回其索引，否则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binarySearch(int nums[],int target){
    int left = 1;
    int right = n;  //这里数组下标从1开始
    while(left <= right){
        int mid = (left+right) / 2;
        if(nums[mid] == target ){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid - 1;
        }
    }

    return -1;
}

Q1:为什么 while 循环的条件中是 <=，而不是 < ？

因为初始化 right 的赋值是数组是最后一个元素的索引，这里使用的数组下标是从1开始的。
如果使用零下标数组，那应该这样写：

1
2
int left = 0;
int right = n-1;    //n-1是数组的最后一个元素索引

使用<=相当于二分查找的区间是左闭右闭的区间，[left,right]，而使用<则相当于左闭右开的区间[left,right)
在以0下标开始的数组来说索引大小为n是越界的。

下面没有特殊说明我们都按照左闭右闭区间来说明。
这个算法中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间，我们不妨称为「搜索区间」(search space)。

什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：

1
2
if(nums[mid] == target)
    return mid;

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

while(left <= right)的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

while(left < right)的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就可能出现错误。

当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

1
2
3
4
5
6
//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

但是，这种方式不如 <= 来的直观

Q2：为什么 left = mid + 1，right = mid - 1？

我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？

当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

那为什么有些是right = mid 或者 left = mid呢？很明显哪些代码用的是左闭右开的搜索区间，而我们这里用的是左闭右闭的搜索区间

参考

详解二分查找算法