二分查找算法概述

二分查找很简单吗？或许二分查找的思想是直观的，但是细节才是程序的核心。看看 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
18
//左闭右闭写法
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//左闭右开写法——推荐使用左闭右开写法
int binarySearch(int nums[],int target){
    int left = 1;
    int right = n+1;              //这里数组下标从1开始
    while(left < right){       // 注意
        int mid = (left+right) / 2;
        if(nums[mid] == target ){
            return mid;
        }else if(nums[mid] > target){
            right = mid;    // 注意
        }else if(nums[mid] < target){
            left = 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)

Q2：left和right如何迭代？

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

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

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

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

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

Q3：此算法有什么缺陷？

答：至此，应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。

比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的时间复杂度了。

Q4：关于左闭右开写法的解释

在了解了左闭右闭写法之后，我们再来看左闭右开的写法

首先，我们先来分析一下右边界 right 的初始值：

  1. 当right=nums.size() 时，初始化的区间就变成了 $[0,right-1]$，也即 $[0,right)$，左闭右开写法
  2. 当right=nums.size()-1时，初始化的区间就变成了 $[0,right]$，左闭右闭写法

在第一种情况下（左闭右开），当 nums[mid] > target 时，需要将区间向左收缩，即 right = mid。
这个做法的逻辑是：既然 mid 位置处大于 target ，而查找区间又是 “ 左闭右开 ”，因此当 right=mid 时，新的查找区间变成了 $[0,mid)$，这样才不会漏掉值。
同理，当 nums[mid] < target 时，需要将区间向右收缩，即 left = mid+1 ，因为在 " 左闭右开 " 的区间下，新的查找区间变成 $[mid+1,right)$ 才不会漏掉值。
当目标值不在序列中时，需要将 while 的条件写成 while(left < right) 而不是写成 while(left<=right) ，这样会引起数组越界。

二分上下界

二分查找的上下界问题其实是为了解决有序数组中出现重复数据时会面临的问题
若序列中有重复的元素,那就不能简单的返回其中一个下标了,用户需要的是返回重复元素的起始下标和终止下标,用来表示范围

这里的二分上下界和上文提到的左右侧边界有所不同

定义

二分下界：第一个大于等于，目标元素target的元素
二分上届：第一个大于，目标元素target的元素

  • 举例：现有一个数组nums = [1,2,2,2,3]，数组采用1下标索引
    其中二分下界的下标就是nums[2]，二分上界就是nums[5]
  • 分析:
    数组中现在有重复的元素，二分下界就是这段重复元素的开始位置，上界就是这段重复元素的结束位置的右侧，正好围绕这段重复元素形成了一个左闭右开的区间，即[2,5)(数组下标)

二分查找的下界

上文提过，二分查找的左侧边界就是要查找的 target 元素的相邻相同元素的左侧下标，也就是重复元素的第一次出现下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lower_bound(int[] nums, int target) {
    // vector数组写法
    // int left = 0;
    // int right = nums.size(); // 注意

    int left = 1;
    int right = n+1;        // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;    //注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

Q1: 为什么 while(left < right) 而不是 <= ?

用相同的方法分析，因为初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

二分查找的上界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int upper_bound(int[] nums, int target) {
    // vector数组写法
    // int left = 0;
    // int right = nums.size(); // 注意

    int left = 1;
    int right = n+1;        // 注意

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left; // 注意
}

Q1: 最后返回为什么还是left

因为我们要返回的是一个左闭右开的区间，我们这里nums[mid] == target时 left = mid + 1，最后我们返回的是[2,5)的5。如果我们返回的是left-1那就是4（即相同元素的右侧边界），那就不是第一个大于 target的元素了，而是最后一个等于 target的元素了

参考

详解二分查找算法
C++实现二分法详解