漫画:什么是二分查找?

栏目: 编程工具 · 发布时间: 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万人收藏的免费计算机科学速成课

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

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


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

查看所有标签

猜你喜欢:

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

Tagging

Tagging

Gene Smith / New Riders / 2007-12-27 / GBP 28.99

Tagging is fast becoming one of the primary ways people organize and manage digital information. Tagging complements traditional organizational tools like folders and search on users desktops as well ......一起来看看 《Tagging》 这本书的介绍吧!

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具