漫画:什么是二分查找?

栏目: 编程工具 · 发布时间: 5年前

内容简介:作者 | 萌蠢的小灰

漫画:什么是二分查找?

漫画:什么是二分查找?

作者 | 萌蠢的小灰

责编 | 胡巍巍

漫画:什么是二分查找?

漫画:什么是二分查找?

—————  第二天  —————

漫画:什么是二分查找?

漫画:什么是二分查找?

漫画:什么是二分查找?

什么意思呢?我们来举两个栗子:

给定一个有序数组 

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)

戳他了解更多↓↓↓

漫画:什么是二分查找?

 热 文推 荐 

阿里撬得动“印度版”抖音吗?

苹果 SwiftUI 踢馆谷歌 Flutter!

☞惊!为拯救美国落伍的 STEM 教育,纷纷出手教老师编程?!

☞程序员爬取 42 年高考数据,告诉你高考为什么这么难?

☞把病毒写到区块链上可以永远不死? 我们做了一个大胆的实验…… | 技术头条

☞新一代私有云来了!看透基于开源生态的产品化

☞Python实现生命游戏

☞B站超全分享!2万人收藏的免费计算机科学速成课

☞敲代码时,程序员戴耳机究竟在听什么?

你点的每个“在看”,我都认真当成了喜欢


以上所述就是小编给大家介绍的《漫画:什么是二分查找?》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

图解机器学习

图解机器学习

杉山将 / 许永伟 / 人民邮电出版社 / 2015-4 / 49

本书用丰富的图示,从最小二乘法出发,对基于最小二乘法实现的各种机器学习算法进行了详细的介绍。第Ⅰ部分介绍了机器学习领域的概况;第Ⅱ部分和第Ⅲ部分分别介绍了各种有监督的回归算法和分类算法;第Ⅳ部分介绍了各种无监督学习算法;第Ⅴ部分介绍了机器学习领域中的新兴算法。书中大部分算法都有相应的MATLAB程序源代码,可以用来进行简单的测试。 本书适合所有对机器学习有兴趣的初学者阅读。 187张图......一起来看看 《图解机器学习》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具