内容简介:作者 | 萌蠢的小灰
作者 | 萌蠢的小灰
责编 | 胡巍巍
————— 第二天 —————
什么意思呢?我们来举两个栗子:
给定一个有序数组
2,5,7,9,12,14,20,26,30
Case 1:
Case 2:
————————————
为什么说这样效率最高呢?
因为每一次选择数字,无论偏大还是偏小,
都可以让剩下的选择范围缩小一半。
给定范围0到1000的整数:
第一次我们选择500,发现偏大了,
那么下一次的选择范围,就变成了1到499:
第二次我们选择250,发现还是偏大了,
那么下一次的选择范围,就变成了1到249:
第三次我们选择125,发现偏小了,
那么下一次的选择范围,就变成了126到249:
以此类推,最坏的情况需要猜测多少次呢?
答案是 log1000 = 10次,
也就是让原本的区间范围进行10次 “折半”。
刚才我们所分析的是猜数字的游戏。
如果我们把场景转换成最初的面试问题:
在包含1000个整型元素的有序数组中查找某个特定整数,
又该如何去做呢?
同样道理,
我们可以首先判断下标是499的元素(因为数组下标从0开始,到999结束),
如果元素大于要查找的整数,
我们再去判断下标是249的元素,
然后判断下标124的元素......
以此类推,直到最终找到想要的元素,
或者选择范围等于0为止。
上述这个过程,
就是所谓的二分查找算法,
查找的时间复杂度是log(n)。
本文仅代表作者的观点,不代表 CSDN 立场。
【End】
作为码一代,想教码二代却无从下手:
听说少儿编程很火,可它有哪些好处呢?
孩子多大开始学习比较好呢?又该如何学习呢?
最新的编程教育政策又有哪些呢?
下面给大家介绍CSDN新成员: 极客宝宝(ID: geek_baby)
戳他了解更多↓↓↓
热 文推 荐
☞惊!为拯救美国落伍的 STEM 教育,纷纷出手教老师编程?!
☞把病毒写到区块链上可以永远不死? 我们做了一个大胆的实验…… | 技术头条
你点的每个“在看”,我都认真当成了喜欢
以上所述就是小编给大家介绍的《漫画:什么是二分查找?》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。