内容简介：作者 | 萌蠢的小灰
作者 | 萌蠢的小灰
责编 | 胡巍巍
————— 第二天 —————
什么意思呢？我们来举两个栗子：
给定一个有序数组
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 教育，纷纷出手教老师编程？！
☞把病毒写到区块链上可以永远不死? 我们做了一个大胆的实验…… | 技术头条
你点的每个“在看”，我都认真当成了喜欢
以上所述就是小编给大家介绍的《漫画：什么是二分查找？》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Practical Algorithms for Programmers
Andrew Binstock、John Rex / Addison-Wesley Professional / 1995-06-29 / USD 39.99
Most algorithm books today are either academic textbooks or rehashes of the same tired set of algorithms. Practical Algorithms for Programmers is the first book to give complete code implementations o......一起来看看 《Practical Algorithms for Programmers》 这本书的介绍吧!
