二分搜索全攻略
Jacksing

在一个有序数组中查找特定值的时候,二分搜索法是一个很常见且高效的思路,该方法也称为折半查找(Binary Search),它是一种效率较高的查找方法,可以在数据规模的对数时间复杂度内完成查找。

但是在实现二分搜索法的时候,边界条件判断,下标变更计算等地方都很容易出现问题,这些错误会直接导致代码进入死循环或者崩溃。所以,除了在算法层面了解该算法,在代码层面也需要为什么,才能完整掌握该算法。

对于二分搜索法的问题,大体上可以分为两类,第一类是找到一个与给定值相同的值,第二类是找到第一个或者最后一个跟给定值相同的值。其实本质上都是在一个特定区间内反复折半查找。

查找特定值

查找特定值是一个最为常见的操作。先看一个从逻辑推理上是正确的算法实现,代码里的注释标记了最容易出问题的五个地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binarySearch(const vector<int> &vec, int target) {
int left = 0;
int right = vec.size() - 1; // 1

while (left <= right) { // 2
int mid = left + (right - left) / 2; // 3
int val = vec[mid];
if (val == target) {
return mid;
}
else if (val < target) {
left = mid + 1; // 4
}
else if (val > target) {
right = mid - 1; // 5
}
}

return -1;
}

第三点

这是最简单理解的一点,所以将其放置在最前面来讲。

两个数相加的时候,一定要注意溢出错误。一般情况下可以先强制转换为 unsigned long long 进行计算,但此处通过俩下标的差值就可以避免这种额外的转换。

第一点

第一点是最为重要的地方,这个初始值决定了后续易错点的代码应该如何写。

除了示例代码的 vec.size() - 1,此处的取值还可以是 vec.size()。这两个值改变的是算法的搜索区间。当取值是 vec.size() - 1 时,算法在闭区间内搜索,值都位于 [left, right] 中。当取值为 vec.size() 时,算法会在左闭右开区间内搜索,值位于 [left, right) 中。后者也意味着 right 永远指向一个不存在的值。

搜索区间能够确定下来之后,后续的代码其实就很容易确定了。

第二点

搜索区间概念能够理解后,此处应该怎么写其实就很容易理解了。

当搜索区间是一个闭区间的时候,leftright 所指向的值都是可访问的且未访问的。随着搜索地进行,这两个下标会逐渐接近。经过一轮搜索下标变更后,最极端的情况是 left 等于 right 了。但是在这个时候,它们所指向的值还没有被搜索到。这里可以构造一个大小为 1 的数组帮助理解。初始化的时候,leftright 都是 0,此时需要进行一次搜索才能判断结果。所以在这个循环判断条件里,left == right 时不能跳出循环。所以在这种情况下,循环的判断条件是 left <= right

当搜索区间是一个左闭右开区间时,left 指向的是可访问的且未访问的,但 right 所指向的值是不可访问的。在标准库的实现中,左闭右开区间的 right 通常用于标记结束节点。同样的,随着搜索地进行,这两个值会不断地接近。此处也可以借助于一个大小为 1 的数组来理解。初始化的时候,left 是 0,right 是 1。在这种极端情况下,left 严格小于 right。如果此时进行搜索,一旦发现 left 指向的值不是目标值,下标进行变更之后,二者的值就相同了,搜索宣告结束。

简而言之,搜索持续进行的条件是 left < right,这点毋庸置疑。但是 left 能不能等于 right 就取决于搜索区间,不同的区间下,right 所代表的含义是不同的。

第四点和第五点

同样的,第四点和第五点也是跟搜索区间相关联。

当搜索区间是闭区间的时候,两个子区间应该被划分为 [left, mid - 1][mid + 1, right]

当搜索区间是左闭右开区间的时候,两个子区间应该被划分为 [left, mid)[mid + 1, right)

不管在哪种搜索区间下,任意一个数都应该只被搜索一次。在此基础上,划分出来的两个子区间都应该跟原先的区间保持一致,这样才能保证一次只排除一个数且后续的搜索区间是正确的。

查找特定值的左边界

对于数组 [1,2,2,2,3]target = 2 的时候,上文的算法只能返回 2 的索引值。如果希望查找 2 这个目标值的左边界,需要对算法做一定的修改。

先来看下示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int leftBound(const vector<int>& vec, int target) {
int left = 0;
int right = vec.size();

while (left < right) {
int mid = left + (right - left) / 2;
int val = vec[mid];
if (val == target) {
right = mid; // 重点
}
else if (val < target) {
left = mid + 1;
}
else if (val > target) {
right = mid;
}
}

return left;
}

原理

这个算法之所以能够找到左边界,重点在于注释所标记的那一句。每次查找到目标值的时候,都会将搜索区间修改为 [left, mid),不断向左边收缩,直到找出所有的目标值为止。

因为搜索区间是一个左闭右开区间,所以搜索的退出条件是 left < right,原因跟查找目标值的算法一样。从这也可以判断出,退出条件是 left == right,所以最后在返回的时候,任意返回一个变量即可。

返回值

寻找左边界的接口所返回的值其实有一个特殊的含义,即小于目标值的数有多少个。所以对于数组 [1, 2, 2, 2, 3] 的返回值可以有如下解释:

  1. 当目标值为 0 时,返回 0,表明该数组有 0 个小于 0 的数
  2. 当目标值为 1 时,返回 0,表明该数组有 0 个小于 1 的数
  3. 当目标值为 2 时,返回 1,表明该数组有 1 个小于 2 的数
  4. 当目标值为 4 时,返回 5,表明该数组有 5 个小于 5 的数

但是这样也带来了一个问题。当返回值为 0 的时候,数组中究竟存不存在目标值呢?所以我们需要破坏左边界返回值的特殊含义,让接口返回值仅仅用于确定目标值左边界的具体下标。一旦不存在该目标值,则返回 -1。

修改后的代码如下所示:

1
2
3
4
5
6
7
8
9
int leftBound(const vector<int>& vec, int target) {
int left = 0;

// ...

if (left >= vec.size()) return -1;
if (vec[left] != target) return -1;
return left;
}

简单解释一下这两句代码。

  • 第一个 if 判断用于排除数组中的值都小于目标值的情况,此时 left 的值会等于数组大小
  • 第二个 if 判断用于区分当 left == 0 时,无法区分是目标值小于数组所有值还是目标值的左边界恰好位于 0 的情况

查找特定值的右边界

还是一样先看示例代码。注意!该代码并不完整:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int rightBound(const vector<int>& vec, int target) {
int left = 0;
int right = vec.size();

while (left < right)
{
int mid = left + (right - left) / 2;
int val = vec[mid];
if (val == target) {
left = mid + 1;
}
else if (val < target) {
left = mid + 1;
}
else if (val > target) {
right = mid;
}
}

return right;
}

原理

这个算法找有边界的原理跟找左边界是一样的。每次找到目标值的时候,都将搜索区间修改为 [mid + 1, right),不断收缩左边界,直接符合退出条件。

返回值

由算法的原理可以看出,每次查找到目标值都会收缩左边界。所以如果不加以操作,最终的返回值其实第一个大于目标值的数值所在下标,该返回值表明数组中小于等于目标值的元素个数。所以对于数组 [1, 2, 2, 2, 3] 的返回值可以有如下解释:

  1. 当目标值为 0 时,返回 0,表明该数组有 0 个小于等于 0 的数
  2. 当目标值为 2 时,返回 4,表明该数组有 4 个小于等于 2 的数
  3. 当目标值为 3 时,返回 5,表明该数组有 5 个小于等于 3 的数
  4. 当目标值为 4 时,返回 5,表明该数组有 5 个小于等于 4 的数

如果希望找到右边界的下标值,这些返回值明显是不正确的。所以需要略作修改,如下所示:

1
2
3
4
5
6
7
int rightBound(const vector<int>& vec, int target) {
// ...

if (right == 0) return -1;
if (vec[right - 1] != target) return -1;
return right - 1; // 重点
}

简单解释一下这段代码:

  1. 第一个 if 用于排除目标值比数组中的值都要小的情况;
  2. 第二个 if 用于排除目标值比数组中的值都要大的情况

需要重点关注的是注释所标记的那句返回值语句,这里提供三个角度的理解方法:

  1. right 作为返回值所表明的含义可知,正确的右边界下标应该是 right - 1
  2. 每次找到目标值的时候,左边界都会进行一次收缩操作,这个操作的代码是 left = mid + 1。所以这里简单变换一下就可以算出,mid = left - 1
  3. 在这个算法里,搜索区间是左闭右开区间,这意味着 right 所指向的位置都是不可访问的,需要向左前进一位才可以访问

其他搜索区间的代码

二分搜索法的搜索区间有两种,上文讲解的时候只采用了其中一种,现在将三种算法不同搜索区间下的代码展示于下面:

查找特定值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int binarySearch(const vector<int>& vec, int target) {
int left = 0;
int right = vec.size();

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

return -1;
}

查找特定值的左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int leftBound(const vector<int>& vec, int target) {
int left = 0;
int right = vec.size() - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
int val = vec[mid];
if (val == target) {
right = mid - 1;
}
else if (val < target) {
left = mid + 1;
}
else if (val > target) {
right = mid - 1;
}
}

if (left >= vec.size()) return -1;
if (vec[left] != target) return -1;
return left;
}

查找特定值的右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int rightBound(const vector<int>& vec, int target) {
int left = 0;
int right = vec.size() - 1;

while (left <= right)
{
int mid = left + (right - left) / 2;
int val = vec[mid];
if (val == target) {
left = mid + 1;
}
else if (val < target) {
left = mid + 1;
}
else if (val > target) {
right = mid - 1;
}
}

if (right < 0) return -1;
if (vec[right] != target) return -1;
return right;
}

这里注意一点,当目标值小于数组中的所有值时,right 的值会小于 0,所以此处需要做规避处理。

总结

由上文的讲解可以看出,正确的代码关键之处就在于搜索区间。只有在理解了搜索区间的基础上,才能够正确的写出相应的代码。

查找特定值和查找左右边界的逻辑其实是一样的,都是查找某一个特定的值,不过查找边界的时候需要额外注意边界的返回值问题,以及容错处理。

  • 本文标题:二分搜索全攻略
  • 本文作者:Jacksing
  • 创建时间:2021-12-13 00:07:24
  • 本文链接:https://wzzzx.github.io/dataStructure/binary-search-raiders/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论