分布式系统,程序语言,算法设计

数据结构与算法(二):二分搜索

概述

以前对二分查找的认识只停留在有序数组查找给定整数上,后来发现一类问题都可以用二分的思想来做,概括来说就是:如果要求的结果所在的集合(值域)和要搜索的数的集合(定义域)存在单调(映射)关系,就可以通过二分思想来解决,说起来有点抽象,后面将用几个例子来说明。

二分思想以其每次迭代将规模砍一半的效率,有着极其广阔的应用。

本文分两大部分,第一部分对二分查找的各个细节探讨;第二部分拓展二分查找为一般的二分思想。

作者:青藤木鸟 https://www.qtmuniao.com, 转载请注明出处

二分查找–边边角角

基本代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int find(vector<int> &arr, int target) {
int left = 0, right = arr.size()-1;

while (left <= right) {
int mid = (left + right) / 2;

if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target){
left = mid + 1;
} else {
right = mid - 1;
}
}

return -1;
}

像上面这一段平平无奇的代码,在实际运用的时候却又诸多变化。二分查找的基本思路不再多说,现在只分析边边角角(Corner Case)。这就涉及到我们一个基本原则,既要让所有元素有可以搜索到的机会,又不至于陷入死循环。具体来说有以下几个问题:

  1. 循环条件。什么时候用left <= right,什么时候用left < right呢?
  2. 取中方式。mid常用的有几种计算方式:mid = (left+right)/2mid = left+(right-left)/2mid = (left+right+1)/2
  3. 边界移动。leftright 都有两种移动方式,拿left来说:left=mid+1left=mid
  4. 最终状态。如果没有查找到指定值,比如说[1,2,3,5]中查找数字4,那么最后跳出循环后,left 和 right 分别指向5和3的位置。也就是说,在4应该插入的位置两侧,并且left > right。

上面的几个问题其实是相互勾连的,视遇到的问题来适当组合。比如说,查找一个有序数组{1, 2, 3, 3, 3, 5}某个数字 {3} 的左右边界下标:[2, 4]

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

while (left < right) {
int mid = left_range ? (left + right) / 2 : (left + right + 1) / 2;
if (arr[mid] == target) {
// Find left boundary: if we round right when calculate mid, then
// we will trap into infinite loop here(imagine
// we only have two elements in the array).
// Find right boundary: the similar reason.
left_range ? right = mid : left = mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return left;
}

上面的代码,在要查找的数字存在的时候是对的,如果不存在需要加额外判断。需要加什么判断呢?这也就是需要说明的另一个地方:当我们进行二分查找的时候,是在中途找到结果就退出(return)呢,还是一直到循环条件被打破退出呢?前者用来最简单的查找指定值,而后者一般是查找某个边界,或者符合条件的最值。该问题因为是由于破坏了循环条件left < right退出的,所以得判断下arr[left]是否和target相等。

因此:

  1. 循环条件,和移动方式和跳出边界时判断相关。

  2. 取中方式,和是否会溢出相关。比如 left 和 right 都很大,则 (left + right)/2 一般。

  3. 边界移动,这个要看是否需要循环最后跳出的左右边界结果,还是仅仅缩小范围。

  4. 最终状态,看是要查找到某个特定值结束,还是需要不断二分直到边界缩小为负值跳出。

推广二分

仔细思考有序数组的二分查找的过程可以得到几个特点:

  1. 数组数值(查找范围)和其下标(查找目标)呈现一种单调的映射关系。
  2. 每次二分,都会砍掉当前数据规模的一半,因此也叫“折半查找”。

单调映射

将二分思想推广,只要查找范围中的数值和目标值所构成的函数是单调的,我们就可以通过比较查找对象,来缩小目标值的范围。

小结

有些点还没想清楚,以后再补充。