bachzart's Blog
0%

二分查找完全笔记

Posted on In ,
Symbols count in article: 2.4k Reading time ≈ 3 mins.

一次性整理了二分查找的很多细节...

前言

二分查找应该是很多人接触数据结构与算法这门课程最先学习的内容了，也即所谓梦开始的地方了吧😂。而之所以会首先接触它，也只是因为它简单罢了。从算法描述、形式和代码复杂程度来讲，它确实简单，可深究一下就会发现，二分查找的细节很多，这也就导致了很多人手写出来的二分查找算法是存在问题的。那么本文的目的，就是完整的整理不同情况下二分查找的写法，并说明这些细节问题。

概念

这里我们不再赘述二分查找的原理，但是需要说明一些概念：

  1. 二分查找的搜索对象被认为是一个区间，整个搜索过程会不断的将区间“折半”。
  2. 每一步搜索完成后，我们都可以知道区间外左边的数全部小于目标值，区间外右边的数全部大于目标值。

分类

既然已经知道了二分查找是以区间为搜索对象来进行查找的，那么就可以按照搜索区间的形式得到几种不同的二分搜索的写法。
为了简单起见，下面的代码就以在普通数组上进行二分查找为例，找到指定元素时会返回其下标，如若找不到指定元素，则会返回其插入位置。

左闭右闭

1
2
3
4
5
6
7
8
9
10
11
12
int lower_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;    // [left, right]
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            left = mid + 1;                    // [mid + 1, right]
        } else {
            right = mid - 1;                // [left, mid - 1]
        }
    }
    return left;
}

左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
int lower_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();        // [left, right)
    while(left < right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            left = mid + 1;                    // [mid + 1, right)
        } else {
            right = mid;                    // [left, mid)
        }
    }
    return left;                            // or right
}

左开右开

1
2
3
4
5
6
7
8
9
10
11
12
int lower_bound(vector<int>& nums, int target) {
    int left = -1, right = nums.size();        // (left, right)
    while(left + 1 < right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            left = mid;                        // (mid, right)
        } else {
            right = mid;                    // (left, mid)
        }
    }
    return right;
}

拓展

注意：以下讨论只对整数成立。

有了上面的讨论，对于二分查找的理解应该已经比较全面了。但在遇到实际问题时，可能直接使用二分查找并不能解决问题。比如，如果需要查找一个数组中严格大于目标值的数，可二分查找返回的是大于等于目标值的值所在位置，这要怎么办呢？
答案是将问题转换一下，查找严格大于目标值的数等价于查找大于等于目标值加一的数，也就是说:
$$ x > target \iff x \ge target + 1 $$

对于类似的问题，总结一下：

问题 等价问题 元素位置
$x \ge target$ $x > target - 1$ first
$x > target$ $x \ge target + 1$ first
$x \le target$ $x < target + 1$ last
$x < target$ $x \le target - 1$ last

现在用lower_bound函数表示二分查找大于等于目标值的第一个元素位置，upper_bound函数表示二分查找严格大于目标值的第一个元素位置，就可以将上述问题继续转化为：

问题 lower_bound upper_bound 元素位置
$x \ge target$ lower_bound(target) upper_bound(target - 1) first
$x > target$ lower_bound(target + 1) upper_bound(target) first
$x \le target$ lower_bound(target + 1) - 1 upper_bound(target) - 1 last
$x < target$ lower_bound(target) - 1 upper_bound(target - 1) - 1 last

需要注意的是：使用lower_bound或upper_bound函数时，如果不存在满足条件的元素，那么+/- 1操作就会导致越界了，所以别忘记先判定一下。

总结

本文整理了二分查找的三种不同写法，这三种写法基于每次查找时的区间大小的不同而不同，分别是：闭区间、左闭右开区间和开区间。
同时，我们还讨论了常见的二分查找问题及对应的等价问题，还有对应的解决方法。
一般来讲，各个编程语言都有二分查找相关的 API 可以使用，但二分查找的逻辑仍然需要牢牢掌握，因为并不是每一次都能直接使用 API。比如，当单个有序文件过大，无法一次性读入内存时，就需要用文件指针和计算偏移量的方式来进行二分查找。对此，就需要手动写出特定版本的二分查找算法。
另外，我们还可以发现，在移动左右区间的位置时，哪边是闭区间，收缩那边时就需要对mid进行加减操作，开区间则不必。

Buy me a coffee ? :)