Just for Life.

明月更几时

0%

算法系列：二分搜索

发表于 更新于
本文字数： 6.4k 阅读时长 ≈ 6 分钟

不能继续开坑了，得整理一下。最近在刷二分法，思路很简单，细节是魔鬼。时而减一时而不用，仿佛在面向玄学编程，所以特意来整理一下。本文参考。

对于最常见的二分查找框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = ...;

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

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。本文都会使用 else if，旨在讲清楚，读者理解后可自行简化。

  1. 其中 ... 标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。
  2. 另外声明一下，计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。

查找一个数

这个场景是最简单的，在一个数组中搜索一个数，如果存在，返回其索引，否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0; 
    int right = nums.size() - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 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;
}

int main() {
    // 0 1 2 3 4 5 6  7  8  9  10
    // 1 3 5 5 8 9 12 23 34 56 84
    vector<int> v{12, 34, 23, 5, 1, 8, 56, 3, 5, 9, 84};
    int target = 23;
    // 有序是使用二分的前提
    sort(v.begin(), v.end());
    int a = binarySearch(v, target);
    cout << a << endl;
    return 0;
}
  1. 为什么 while 循环的条件中是 <=，而不是 <？因为初始化 right 的赋值是 nums.length - 1，而不是 nums.length。这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)。我们这个算法中使用的是前者 [left, right] 两端都闭的区间，这个区间其实就是每次进行搜索的区间。
  2. 那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
  3. 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，或者时而减时而不减，到底怎么回事，怎么判断？答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？之前提到搜索区间是闭区间，所以当然是去搜索 [left, mid-1] 或者 [mid+1, right] ，因为 mid 已经搜索过，应该从搜索区间中去除。之后还有有这方面的细节。
  4. 扩展一些，如果不返回 -1 而是直接返回 left。如果数字在数组中，返回的就是索引；如果不在数组中且以升序为例，返回的就是这个元素插入数组中应该放到哪个位置。
  5. 而对于 while(left < right) 这种情况，也就是搜索区间是 [left, right)，那么终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 的第一个 2 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。我们已经知道了出错的原因，就打个补丁好了：
    1
    2
    3
    4
    while(left < right) {
        // ...
    }
    return left < right ? left : -1;

搜索左侧边界

给定一个数组，1 2 2 2 3，搜索数字 2 最开始出现的左侧区间，这里就返回索引 1。代码如下，这里写成左闭右开的形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0; 
    int right = nums.size(); // 注意

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

int main() {
    // 0 1 2 3 4 5 6  7  8  9  10
    // 1 3 5 5 8 9 12 23 34 56 84
    vector<int> v{12, 34, 23, 5, 1, 8, 56, 3, 5, 9, 84};
    int target = 1000;
    sort(v.begin(), v.end());
    int a = binarySearch(v, target);
    cout << a << endl;
    return 0;
}
  1. 为什么 while 中是 < 而不是 <=? 用相同的方法分析，因为 right = nums.length 而不是 nums.length - 1。因此每次循环的「搜索区间」是 [left, right) 左闭右开。while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止。
  2. 如果 nums 中不存在 target 这个值，怎么办？对于一个数组 1 2 2 2 3，target 为 2 返回 1，含义是：nums 中小于 2 的元素有 1 个；target = 1，算法会返回 0，nums 中小于 1 的元素有 0 个；target = 8，算法会返回 4，nums 中小于 8 的元素有 4 个。综上可以看出，函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]，所以我们简单添加两行代码就能在正确的时候 return -1。
  3. 为什么 left = mid + 1，right = mid 和之前的算法不一样？因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。
  4. 为什么返回 left 而不是 right？都是一样的，因为 while 终止的条件是 left == right。
  5. 能不能想办法把 right 变成 nums.length - 1，也就是继续使用两边都闭的「搜索区间」？这样就可以和第一种二分搜索在某种程度上统一起来了。由于 while 的退出条件是 left == right + 1，所以当 target 比 nums 中所有元素都大时，会存在以下情况使得索引越界。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include <iostream>
    #include <algorithm>
    #include <vector>

    using namespace std;

    int binarySearch(vector<int>& nums, int target) {
        int left = 0; 
        int right = nums.size() - 1; // 注意

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

    int main() {
        // 0 1 2 3 4 5 6  7  8  9  10
        // 1 3 5 5 8 9 12 23 34 56 84
        vector<int> v{12, 34, 23, 5, 1, 8, 56, 3, 5, 9, 84};
        int target = 1000;
        sort(v.begin(), v.end());
        int a = binarySearch(v, target);
        cout << a << endl;
        return 0;
    }

寻找右侧边界

给定一个数组，1 2 2 2 3，搜索数字 2 最开始出现的最右侧区间，这里就返回索引 3。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    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 nums[left-1] == target ? (left-1) : -1; // 注意
}
  1. 搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。
  2. 为什么最后返回 left - 1 而不像左侧边界的函数，返回 left ？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。
  3. 至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在等式条件 nums[mid] == target 下的判断：left = mid + 1，因为最后一定是找到了和 target 相等的数字，且是最右侧的。对 left 的更新是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0; 
    int right = nums.size(); // 注意

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

int main() {
    // 0 1 2 3 4 5 6  7  8  9  10
    // 1 3 5 5 8 9 12 23 34 56 84
    vector<int> v{12, 34, 23, 5, 1, 8, 56, 3, 5, 9, 84};
    int target = 34;
    sort(v.begin(), v.end());
    int a = binarySearch(v, target);
    cout << a << endl;
    return 0;
}

STL 开车

对于一些高级语言而言，其实都内置了二分搜索。以 C++ 为例，搜索数组 1 2 2 2 3 中有几个 2。第一种方案是搜索 2 出现的左边界，而后搜索出现的右边界。但是也可以通过 lower_bound 和 upper_bound 来解决，因为在某些复杂应用下，二分只是一个小点，没必要花费大多精力在不重要的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

    vector<int> v{1, 2, 2, 2, 3};
    int target = 2;
    vector<int>::iterator lower, upper;

    lower = lower_bound(v.begin(), v.end(), target);
    upper = upper_bound(v.begin(), v.end(), target);

    cout << static_cast<int>(upper - lower) << endl;

    return 0;
}
本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章