聊聊算法——二分查找算法深度分析
今天我想说下二分查找算法,可能各位看官都觉得二分查找很简单,没啥可说的,但魔鬼在细节,二分查找的各临界值处理,
二分查找的局限性,二分查找的变形算法,甚至是衍生出来的三分查找、四分查找,都值得思考一番,如此经过一番折腾,
或许才算真正掌握了二分查找算法的精髓了!
作者原创文章,谢绝一切转载,违者必究!
本文只发表在"公众号"和"博客园",其他均属复制粘贴!如果觉得排版不清晰,请查看公众号文章。
准备:
Idea2019.03/JDK11.0.4
难度: 新手--战士--老兵--大师
目标:
- 深度理解二分查找算法
1 算法框架
先看二分算法框架:
private static int binary_search(List<Integer> list,int target){
int left = 0;
int right = list.size()-1;
while (...){
int mid = left + (right - left)/2;
if (list.get(mid) == target){
right = ...;
}
else if (list.get(mid) > target){
right = ...;
}else if (list.get(mid) < target){
left = ...;
}
}
return ...;
}
思路很简单:对有序列表先比较中间位置的数,如果相等,即找到目标;如果中间值比目标值大,则在小端的一半范围内查找;
如果中间值比目标值小,则在大端的另一半范围去查找,如此迭代下去。
这里我提出几个问题:
1.left + (right - left)/2 为啥不直接写成 (left + right)/2?
2.中间值mid为非整数时有无问题?
3.right是否可以写为right = list.size()?
答:1 (left + right)很大时可能会int越界,而left + (right - left)/2 则安全;
2 mid为非整数时,由于int类型限制,会自动转换处理,只会导致分割出来的两个范围长度不等,但不影响最终结果;
3可以写为right = list.size(),但while循环中的终止条件则需要对应调整,见后文分析;
2 小试牛刀
有了框架,再来解决问题,先来个常规的二分查找:输出目标值在列表中的序号值,没有则输出 -1 ,java完整版:
public class BinarySearch {
public static void main(String[] args) {
List<Integer> nums = Arrays.asList(6, 7, 8, 1, 2, 3, 4, 5);
Collections.sort(nums);
System.out.println(nums);
int res = findIndex(nums,1);
System.out.println(res);
}
private static int findIndex(List<Integer> list,int target){
int left = 0;
int right = list.size() -1;
while (left <= right){
int mid = left + (right - left)/2;
System.out.println("mid >> "+ mid);
if (list.get(mid) == target){
return mid;
}else if (list.get(mid) < target){
left = mid +1;
}else if (list.get(mid) > target){
right = mid -1;
}
}
return -1;
}
请看官思考问题:
1.如果上面写为right = list.size(),会发生什么? 答:若如此,则可知list.get(list.size()) 是越界的。而while (left <= right) 的循环终止条件
为left > right,即达到 left = right + 1时,设想target比所有值大时,最终会mid= list.size(),发生越界异常。
2.如果我非要写为right = list.size(),可以吗? 答:若修改代码为while (left < right) ,则循环终止条件为left = right,即使target比所有值都
大时,也只会达到left = right= list.size(),而此时已经终止循环,不会发生越界,故理论上可行。
3.如果写为right = list.size(),有无算法漏洞? 答:由上可知,while (left < right)循环终止条件为left = right,对于以上示例代码,当查
找target为1时,循环终止条件为left = right=0,而此时循环已经终止,最终导致漏掉了list.get(0)的元素,输出为-1,因此我们需补上漏洞:
//return -1;
return list.get(left) == target? left : -1;
3 进阶思考
如果我们遇到数组 {1, 2, 3, 3, 3, 4, 5, 6, 7, 8} ,还是运用上面二分查找算法,会是什么结果?若采用right = list.size()-1写法,则答案是4,
因为第一次mid直接匹配成功即结束;若采用right = list.size()写法,则答案是2,因为第二次mid匹配成功即结束,由此可见常规二分查找
还是有其局限性的,需要求元素唯一;那么现在题目要求变为,找出最左侧匹配目标的序号值,即左侧边界,如何来利用二分查找框架来改写实现?
分析:需要寻找左侧边界,那么我们在每次二分的时候,就应该缩小右侧边界,直到循环终止。 先给出一个可行代码方案A:
private static int left_bound(List<Integer> list,int target){
int left = 0;
int right = list.size();
while (left < right){
int mid = left + (right - left)/2;
if (list.get(mid) == target){
right = mid;
}
else if (list.get(mid) > target){
right = mid;
}else if (list.get(mid) < target){
left = mid + 1;
}
}
return left;
}
以上代码分析:
1.寻找左边界,每次二分,若中间值等于目标,左边界肯定不会在右侧大端范围,只能是中间值位置或左侧小端范围,于是固定搜索范围
右侧right=mid;若中间值小于目标,左边界肯定在右侧大端,而且可以缩小搜索范围为left = mid + 1;若中间值大于目标,左侧边界肯定
在左边小端,而且可以缩小搜索范围为right = mid – 1,但是同时while (left < right)的结束条件是left = right,如果目标值比列表所有元素
都小,最终会导致left=-1,发生越界,故这里应该写为left = mid,即right = mid – 1也是可以的,如果非要这么写,就需要处理临界值情况;
2.如果需要找不到目标值时返回-1,则可以修改最后的代码为:
//return left;
if (left == 0 && list.get(left)!=target){
return -1;
}
return list.get(left) == target ? (left) : -1;
如果写为right = list.size() – 1 的方案B,也是可行的,需非常仔细观察与A的差异:
private static int left_bound_B(List<Integer> list,int target){
int left = 0;
int right = list.size() - 1; //差异
while (left <= right){ //差异
int mid = left + (right - left)/2;
if (list.get(mid) == target){
right = mid - 1; //差异
}
else if (list.get(mid) > target){
right = mid - 1; //差异
}else if (list.get(mid) < target){
left = mid + 1;
}
System.out.println("left"+left);
System.out.println("right"+right);
}
return left;
}
以上代码分析:初始化right = list.size() – 1,则循环条件应该写为while (left <= right),因为while (left < right) 遗漏了left = right= list.size() – 1的
临界值,且因为while (left <= right)的终止条件是 left=right + 1,当二分匹配时,如果中间值等于目标值,则左侧边界肯定是目标值或者在左侧
小端范围内,但同时为了使得循环能退出,故缩小右侧搜索范围为right = mid – 1,如果写为right = mid,则可知此时left = right=mid,不满足
退出条件,并进入下一次循环,然后无限循环下去,即死循环了!如果中间值小于目标值,则左侧边界肯定是在右边大端范围内,同理,也是为
了满足循环退出条件,缩小搜索范围为left = mid + 1;如果中间值大于目标值,分析类似,略!
如果需要找不到目标值返回 -1 ,则可以修改最后的返回值。这里需考虑临界值情况为:目标值比所有值都小,left=0,right=-1;目标值比所有值
都大,left=list.size(),right=list.size()-1,故修改返回值为:
if (left == list.size() && list.get(left-1) != target){
return -1;
}
return left==0 && list.get(left) != target ? -1: left;
思考题: 留个作业,写个右侧边界搜索算法,请看官思考一下吧!请不要只是脑海里闪过几行代码,那只能说明这个算法还在我这。
全文完!
我近期其他文章:
- 1 DevOps系列——Jenkins/Gitlab自动打包部署
- 2 DevOps系列——Jenkins私服
- 3 DevOps系列——Gitlab私服
- 4 聊聊算法——滑动窗口
- 5 聊聊算法——回溯算法
只写原创,敬请关注
推荐阅读
-
05.数据的深度分析(数据挖掘、机器学习)--《数据科学概论》-二、具体的机器学习算法
-
聊聊算法——二分查找算法深度分析
-
改进版的二分查找加速插入排序算法
-
【摩尔线程+Colossal-AI强强联手】MusaBert登上CLUE榜单TOP10:技术细节揭秘 - 技术实力:摩尔线程凭借"软硬兼备"的技术底蕴,让MusaBert得以从底层优化到顶层。其内置多功能GPU配备AI加速和并行计算模块,提供了全面的AI与科学计算支持,为AI推理和低资源条件下的大模型训练等场景带来了高效、经济且环保的算力。 - 算法层面亮点:依托Colossal-AI AI大模型开发系统,MusaBert在训练过程中展现出了卓越的并行性能与易用性,特别在预处理阶段对DataLoader进行了优化,适应低资源环境高效处理海量数据。同时,通过精细的建模优化、领域内数据增强以及Adan优化器等手段,挖掘和展示了预训练语言模型出色的语义理解潜力。基于MusaBert,摩尔线程自主研发的MusaSim通过对比学习方法微调,结合百万对标注数据,MusaSim在多个任务如语义相似度、意图识别和情绪分析中均表现出色。 - 数据资源丰富:MusaBert除了自家高质量语义相似数据外,还融合了悟道开源200GB数据、CLUE社区80GB数据,以及浪潮公司提供的1TB高质量数据,保证模型即便在较小规模下仍具备良好性能。 当前,MusaBert已成功应用于摩尔线程的智能客服与数字人项目,并广泛服务于语义相似度、情绪识别、阅读理解与声韵识别等领域。为了降低大模型开发和应用难度,MusaBert及其相关高质量模型代码已在Colossal-AI仓库开源,可快速训练优质中文BERT模型。同时,通过摩尔线程与潞晨科技的深度合作,仅需一张多功能GPU单卡便能高效训练MusaBert或更大规模的GPT2模型,显著降低预训练成本,进一步推动双方在低资源大模型训练领域的共享目标。 MusaBert荣登CLUE榜单TOP10,象征着摩尔线程与潞晨科技联合研发团队在中文预训练研究领域的领先地位。展望未来,双方将携手探索更大规模的自然语言模型研究,充分运用上游数据资源,产出更为强大的模型并开源。持续强化在摩尔线程多功能GPU上的大模型训练能力,特别是在消费级显卡等低资源环境下,致力于降低使用大模型训练的门槛与成本,推动人工智能更加普惠。而潞晨科技作为重要合作伙伴,将继续发挥关键作用。
-
用C++实战演示二分查找算法实例
-
算法小秘诀3:快速掌握二分查找全解
-
当我编排二分查找算法时,内心所想与步骤解析
-
二分查找算法
-
深度学习日-25:入门-V1 算法实践与分析
-
【Java算法】二分查找 下