如何写出无bug的二分查找

原理

二分查找算法是一种在有序数组中查找特定元素的查找算法,查找过程从数组的中间元素开始。

创新互联专业为企业提供久治网站建设、久治做网站、久治网站设计、久治网站制作等企业网站建设、网页设计与制作、久治企业网站模板建站服务,十载久治做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。

  • 如果中间元素刚好是要查找的元素,则查找结束。
  • 如果比中间元素的值小,则在数组起始到小于中间元素的那一半之间查找,而且也是从这一半儿的中间位置开始比较。
  • 如果比中间元素的值大,则在数组大于中间元素到末尾元素的那一半儿之间查找,同样还是从这一半儿的中间位置开始比较。

这里有一个有序数组,元素的索引从 0 到 6,我们以它为例来说明二分查找的过程:

  • 查找值为 15 的元素;

15 刚好位于数组中间的位置,所以比较一次就找到了;

  • 查找值为 8 的元素;

数组中间位置的元素是 15,目标值 8 小于 15,所以查找范围缩小到 15 左边的一半,也即 [ 3 , 9 ] ,这一半中间位置的元素是 8,刚好是要查找的值;

  • 查找值为 34 的元素;

数组中间位置的元素是 15,目标值 34 大于 15,所以查找范围缩小到 15 右边的一半,也即 [ 19 , 34] ,它们的中间元素是 20,目标值 34 比 20 大,所以查找范围继续减半为 [ 34, 34 ] , 它们的中间元素是 34, 刚好是要查找的值。

基本框架

根据上述二分查找的流程,可以总结出二分查找的基本框架, 下面是伪代码:

int binary_search(vector &vec, int target)
{
int left = 0; //查找范围的左边索引
int right = 0; //查找范围的右边索引
while(...) //查找结束条件
{
//数组中间元素的索引
int mid = left + (right - left) / 2;
//和目标值相等
if(target == vec[mid])
{
//处理逻辑
...
}
//目标值小于中间元素
else if(target < vec[mid])
{
//处理逻辑
left = ...
}
//目标值大于中间元素
else
{
//处理逻辑
right = ...
}
}
//返回目标值在索引中的位置,如果找不到,返回 -1
return ...
}

伪代码中的 ... 的地方是容易出现细节问题的地方, 我们自己编写或者看别人代码的时候,注意下这些地方。

需要注意一点,计算查找范围的中间位置的索引的方法 mid = (left + right) / 2, 当数组非常大的时候, left + right 可能会超过整形最大值,所以需要修改成 mid = left + (right - left) / 2 或者 mid = left + (right - left) >> 1, 以避免溢出风险。

实现

二分查找的实现方式有多种,这里只选取前面基本框架中的方式来介绍,常见的二分查找场景有:查找一个指定的数、查找数组中第一个和目标值相等的元素,查找数组中最后一个和目标值相等的元素。

下面的算法实现代码是用 C++ 语言实现的,vector vec 表示一个整形的数组, 数组名是 vec ,类似于 Java 中的 int[] nums, 如果是 C语言的话,可以用 int *nums 和 int len 来表示也是一样的,大家可以自行用熟悉的编程语言实现。

1. 查找和目标值相等的元素

这是最基础的二分查找,只要找到了和目标值相等的元素,返回其索引,否则返回 -1,表示没找到和目标值相等元素的索引:

int binary_search(vector &vec, int target)
{
int ilen = (int)vec.size();
if(ilen <= 0) return -1;
int left = 0;
int right = ilen - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
//找到了,直接返回
if (target == vec[mid]) return mid;
if(target < vec[mid]) right = mid -1;
else left = mid + 1;
}
return -1;
}

需要注意几点:

  • 为什么 while 的循环条件是 <=;

因为 right = ilen - 1 , 也就最后一个元素的索引, 当 left 等于 right 的时候, 表示 到达查找范围右边的边界。

此时 mid = left = right, 当 mid 索引处的元素和目标值相等时, 返回索引 mid。

如果不相等, 要么 left = mid + 1 要么 right = mid -1 ,不管执行哪个逻辑,结果都是 left > right, 接着退出 while 循环。

  • 为什么 left = mid + 1 或者 right = mid - 1;

根据前面的介绍可知,二分查找的范围是 [left, right], 当我们发现查找的目标值不等于 mid 索引元素的值时, 下一次查找的范围是 [left, mid - 1] 或者 [mid + 1, right], 因为 mid 处的元素已经比较过了,需要从查找范围中排除。

2. 第一个和目标值相等的元素

上面的二分查找有一个局限性,比如一个有序数组 {-1,-1,-1,-1,2,3}, target 的值为 -1, 此时算法返回的索引是 2, 结果是没错,但如果我想得到第一个和 target 相等元素的索引,也即 0 或者最后一个和 target 相等元素的索引, 也即 3 时, 此算法是没办法处理的, 下面就来说明这两种二分查找算法。

int binary_search_firstequal(vector &vec, int target)
{
int ilen = (int)vec.size();
if(ilen <= 0) return -1;
int left = 0;
int right = ilen - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
//找到了目标,继续向左查找目标
if (target == vec[mid]) right = mid - 1;
else if(target < vec[mid]) right = mid -1;
else left = mid + 1;
}
if(left < ilen && vec[left] == target) return left;
return -1;
}

当条件 target == vec[mid] 以及 target < vec[mid] 成立时,都执行 right = mid - 1的逻辑, 这里把它们分开是为了便于大家理解,熟练以后,两个条件合并成一个。

  • 为什么 target == vec[mid] 时 right = mid - 1;

当 mid 索引处的值和目标值相等时, 我们需要在 mid 的左边继续查找 , 看是否存在和目标值相同的元素, 所以查找范围变成了 [ left, mid - 1] , 故需要执行 right = mid - 1的逻辑。

  • 为什么最后返回时要加上 left < ilen && vec[left] == target 的条件;

while 循环退出条件是 left = right + 1, 当 target 的值比数组中元素的值都大的时候, left 索引的值会超过数组的最大索引, 所以需要进行索引边界校验,也即 left < ilen。

当 target 的值处于数组最大元素和最小元素之间且数组中不存在和target 值相等的元素时, 此时无法找到一个索引,使得元素的值和 target 相等, 所以,还需要进行 vec[left] == target 的逻辑判断。

  • 为什么返回 left 而不是 right;

也可以返回 right, 把最后的判断改成 if ( right + 1 < ilen && vec[right + 1] == target) return right+1; 即可。

当找到数组中第一个和目标值相等的元素时, 执行了 right = mid - 1, 然后就退出了 while 循环, 而实际的索引值应该是 mid , 也就是 right + 1。

3. 最后一个和目标值相等的元素

和 查找第一个和目标值相等的元素 算法稍有不同, 此二分查找算法找到和目标值相等元素之后,查找范围需要往右移动,继续找下一个和目标值相等的元素。

int binary_search_lastequal(vector &vec, int target)
{
int ilen = (int)vec.size();
if(ilen <= 0) return -1;
int left = 0;
int right = ilen - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
//找到了目标,继续向右查找目标
if (target == vec[mid]) left = mid + 1;
else if(target < vec[mid]) right = mid -1;
else left = mid + 1;
}
if(left - 1 < ilen && vec[left - 1] == target) return left - 1;
return -1;
}

有几个细节需要注意下:

  • 为什么 target == vec[mid] 时 left = mid + 1;

当 mid 索引处的值和目标值相等时, 我们需要在 mid 的右边继续查找 , 看是否存在和目标值相同的元素, 所以查找范围变成了 [ mid + 1, right] , 故需要执行 left = mid + 1的逻辑。

  • 为什么最后返回时要加上 left - 1 < ilen && vec[left - 1] == target 的条件;

当 target 大于或者等于数组中元素的时候, 查找范围左边的边界会右移,即 left = mid + 1, 即使找到了最后一个和目标值相等的元素时,left 还是会向右移动一个位置,所以,实际的位置是 left - 1 而不是 left。

当 target 的值处于数组最大元素和最小元素之间且数组中不存在和target 值相等的元素时, 此时无法找到一个索引,使得元素的值和 target 相等, 所以,还需要进行 vec[left-1] == target 的逻辑判断。

小结

本文介绍了二分查找算法的原理以及常见的实现方式,网上还有很多其他的实现方式,比如:递归的方式、左闭右开的查找范围的方式,它们的原理都是一样的,只是在细节上有差别,只要弄清楚了本文介绍的所有细节处理的原因,其他版本的二分查找是很容易就能弄明白的。

本文题目:如何写出无bug的二分查找
文章起源:http://www.gawzjz.com/qtweb/news49/174049.html

网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联