在计算机科学中,二分搜索(binary search),也称折半搜索(half-interval search)、对数搜索(logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
问题 1
给定一个有序的数组,查找 value 是否在数组中,不存在返回 -1。
例如:{ 1, 2, 3, 4, 5 } 找 3,返回下标 2(下标从 0 开始计算)。
/* 注意:题目保证数组不为空,且 n 大于等于 1 ,以下问题默认相同 */
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
// 如果这里是 int right = n 的话,那么下面有两处地方需要修改,以保证一一对应:
// 1、下面循环的条件则是 while (left < right)
// 2、循环内当 array[middle] > value 的时候,right = middle
while (left <= right) // 循环条件,适时而变
{
int middle = left + ((right - left) >> 1); // 防止溢出,移位也更高效。同时,每次循环都需要更新。
if (array[middle] > value)
right = middle - 1;
else if (array[middle] < value)
left = middle + 1;
else
return middle;
// 可能会有读者认为刚开始时就要判断相等,但毕竟数组中不相等的情况更多
// 如果每次循环都判断一下是否相等,将耗费时间
}
return -1;
}
问题 2
给定一个有序的数组,查找第一个等于 value 的下标,找不到返回 -1。
例如:{ 1, 2, 2, 2, 4 } 找 2,返回下标 1(下标从 0 开始计算)。
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
while (left <= right)
{
int middle = left + ((right - left) >> 1);
if (array[middle] >= value) // 因为是找到最小的等值下标,所以等号放在这里
right = middle - 1;
else
left = middle + 1;
}
if (left < n && array[left] == value)
return left;
return -1;
}
如果问题改为 "查找 value 最后一个等于 value 的下标" 呢?只需改动两个位置:
if (array[middle] >= value)
中的等号去掉;if (left < n && array[left] == value) return left;
改为
if (right >= 0 && array[right] == value) return right;
问题 3
给定一个有序的数组,查找第一个大于等于 value 的下标,都比 value 小则返回 -1。
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n - 1;
while (left <= right)
{
int middle = left + ((right - left) >> 1);
if (array[middle] >= value)
right = middle - 1;
else
left = middle + 1;
}
return (left < n) ? left : -1;
}
如果问题改为 "查找最后一个小于等于 value 的下标" 呢?只需改动两个位置:
if (array[middle] >= value)
的等号去掉;return (left < n) ? left : -1
改为return (right >= 0) ? right : -1
。
左闭右闭 vs 左闭右开
数学上区间边界有开闭之分,对一个区间的表示,我们会有四种表示方法,比如 { 2, 3, ... , 12} 的表示方法如下,
$$ \begin{align} &2≤i<13\\ &1<i≤12\\ &2≤i≤12\\ &1<i<13 \end{align} $$
左闭右闭和左闭右开是最符合人类自然逻辑的区间表示方法。
Dijkstra 早在 1982 年就对这四种区间表示方法的优劣进行了论述,详见链接 https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF。结论是左闭右开是表示区间最友好的方式,因为:
- 上下界之差正好等于元素的个数;
- 在表示两个相邻子序列时相当方便和简洁,一个子序列的上界就是另一个子序列的下界;
- 当上界等于下界时即可表示空集,不会出现上界小于下界的情况。而左闭右闭在表示空集时就会出现上界小于下界的情况,比较难看,比如 $0≤x<=-1$。
左闭右开表示法在编程中处理线性序列问题时对边界情况非常友好。事实上,编程中出现了左闭右开的大量应用。比如 C++ 的 STL、Golang 和 Python 的切片操作...
二分算法中用左闭右闭更容易让人理解,所以上面的代码我使用的都是这种表达方式,不过我还是要讲一讲左闭右开的方式,代码如下(只针对问题一),
int BinarySearch(int array[], int n, int value)
{
int left = 0;
int right = n; // 右开
while (left < right) // 变动一
{
int middle = left + ((right - left) >> 1);
if (array[middle] > value)
right = middle; // 变动二
else if (array[middle] < value)
left = middle + 1;
else
return middle;
}
return -1;
}
这里需要解释的是,变动一和变动二为什么这样变化?
首先,我们要看明白一件事:while (left < right)
只能遍历区间 [left, right)
这个事实!这点是很好理解的。
接下来再看变动一。left <= right
等价于 left < right + 1
,也就是说,程序会遍历区间 [left, right + 1)
,而一开始 right 被初始化为 n 无疑可能会造成数组越界。
而变动二,可以这样去想,if (array[middle] > value)
只能说明当前的 middle 下标处数值是不符合条件的,但 middle - 1 却可能符合,再联系我上面所讲的那个事实,就很明了了。
参考
其它
文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。
如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。
(文章完)