当前位置 博文首页 > 程序员漫话编程的博客:算法 | 深度分析二分查找算法
编者荐语:
大家好,我是你们的朋友 朋哥。
我一直 都认为 算法 很简单? 当然包括二分查找也很简单,但事实真的如此吗?二分查找真的很简单吗?其实并不简单。看看 Knuth 大佬(发明 KMP 算法的那位)怎么说的:
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...
这句话可以这样理解:思路很简单,细节是魔鬼。
其实我们在看一个算法题的时候记起来很简单,真正使用的时候却不是这么简单的。
最起码使用场景和具体需求理解起来还是比较吃力的。
简介
基本思想:又叫折半查找,要求待查找的序列有序,是一种快速查找算法,时间复杂度为 O(logn),要求数据集为一个有序数据集。
使用
应用场景:一般用于查找数组元素,并且数组在查找之前必须已经排好序(一般是升序)。
最常用的二分查找场景:寻找一个数、寻找左侧边界、寻找右侧边界。
步骤:
1、取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,
2、如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。
3、直到查找到了为止,否则序列中没有待查的关键字。
代码示例:
这个场景是最简单的,可能也是大家最熟悉的,即搜索一个数,如果存在,返回其索引,否则返回 -1。
public?static?int?biSearch(int?[]array,int?a){
????int?lo=0;//左
????int?hi=array.length-1; //右
????int?mid;
????while(lo<=hi){
????????mid=(lo+hi)/2;//中间位置
????????if(array[mid]==a){
????????????return?mid;
????????}else?if(array[mid]<a){?//向右查找
????????????lo=mid+1;
????????}else{?//向左查找
????????????hi=mid-1;
????????}?
??}
????return?-1;
}
?
这里会有一个疑问:为什么 while 循环的条件中是 <=,而不是 < ?
因为初始化 right 的赋值是?array.length-1,即最后一个元素的索引,而不是?array.length。
这二者可能出现在不同功能的二分查找中,区别是:前者相当于两端都闭区间 [left, right],后者相当于左闭右开区间 [left, right),因为索引大小为?array.length?是越界的。
我们这个算法中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间,称为「搜索区间」(search space)。
?
因为我们初始化 right = array.length-1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while ((lo<=hi)
同时也决定了 left = mid+1 和 right = mid-1
因为我们只需找到一个 target 的索引即可
所以当 array[mid] == target 时可以立即返回
?
原创不易,有用就关注一下。要是帮到了你 就给个三连吧,多谢支持。
觉得不错的小伙伴,记得帮我 @程序员漫话编程**,点个赞和关注哟,笔芯笔芯~**
来源:公众号「程序员漫话编程」
作者:耳东双月
原文链接:https://mp.weixin.qq.com/s/OJXzQEtVDsPfrPmNy-fDpw
附程序员必备小册,小册版权归作者所有,GitHub 地址:
github.com/ProceduralZ…
cs