动画:二分查找(上) | 面试官问我如何在 1 亿数据中快速查找某一整数?

5,114 阅读7分钟
关注公众号,小鹿动画学编程,一天一篇动画喂饱你!

文章写作加动画制作连续好几个小时,作者不是铁人做着,也会出现精力不足的情况,文章中难免出现笔误或者动画错误,但是挡不住小鹿分享的步伐,不喜欢就勿喷哦,喷也可以,你可喷不过我的哦!哈哈哈哈!

------ 一下是正文 -----------

写在前边

今天就来学习一下在一组有序数据中如何快速查找一个数。也就是我们所说的二分查找,虽然很多小伙伴对二分查找很熟悉,但是到了真正的应用问题上,还是不能更好的来把握二分的思想。要想把这部分把握好,还需要真正的体验一下二分查找的强大的效率。

如题目中所述,如果你今天去面试,面试官要问你如何在十个数中查找一个整数,那么你很快就会想到从头到尾遍历就可以。

但是随着面试难度的加大,面试官会问你如何在 10 万、100万、1000万甚至一个亿数据中查找一个数,你该如何解决?要想达到效率最低,空间消耗的少,那不得不走进今天的二分查找。

目录

一、什么是二分查找

二分查找在生活中无处不在,举个例子。我们有没有小时候玩过猜数字的游戏,给你一组数字,我拿出一个数字,你每猜一个数,我就会告诉你你猜的数和正确的数的大小关系,然后再继续猜,直到猜到为止。

当时玩的时候,基本就是瞎猜。那我们想想如何做到最快的能够猜出它的正确值是多少?我们每次可以取最小值和最大值中间的数字来猜,如果小于正确数字我们再进行折中,直到猜到为止,这是最快的查找方法。

通过这个例子,想必你已经掌握了二分的思想。小结一下,就是在一个有序数据中,将数据折中,每次折中的数据和要查找的数据进行对比,然后不断的缩小查找的区间,直到查找到或者区间为 0 为止。

二、动画实现

在这里插入图片描述

三、二分查找的性能

既然我们说二分查找很快,那到底快到那?有多快?总之不能口头说吧?

那我们就证明一下,假设我们有 n 个数据,每次查找都会折半,也就是 n/2。最好情况是一次就能查找到,最坏的情况就是最后一次才可以查找到。其实这就是涉及到我们高中的数学中的问题,如下图:

在这里插入图片描述
假设我们折半了 m 次之后不能再折半了,每次折半只需完成对比操作,经过 m 次折半之后,n/2的 m 次方等于 1,那么m = log2n。我们可以得到时间复杂度为O(logn)。

那么问题来了,O(logn)的时间复杂度执行效率高吗?那我们看文章中面试官给出 1 亿数据只需查找大约 26 次,可以看出效率非常高了。

其实对数对应相反的就是指数,指数大家都很了解吧,越到后边越是疯狂指数增长。

四、二分实现的三个重点

上边我们已经把二分查找的思想掌握了,那我们开始动手写写代码。据了解,二分查找的出现和实现一个正确的二分查找代码中间相差了 16 年的时间,可以看出二分查找涉及到的细节还是挺多的,但是古人总结了,我们记住,知道为什么,理解了写出一个二分查找还是很容易的。

1、JavaScript 版本

在这里插入图片描述

2、Java 版本

3、C 语言版本

在这里插入图片描述

4、Python 版本

4.1 循环退出条件

假如我们在循环退出的时候,让low指针小于high指针,而不是等于,会出现什么问题呢?这一步大家一定用代码去实践一遍才会印象深刻。这个问题留给大家,下边留言区说出你的实践,答对者,小鹿奖励红包一个。

4.2 中位数的取值

我们一般取中位数的值是(low + hight)/ 2。那么问题来了,如果low和high的和超出了整数的范围我们咋办?

有两种解决办法,第一种是用low+(high-low)/2的方式,另外一种是用位运算low+((high-low) >> 1)。

4.3 两个指针的移动

所谓的两个指针的位置移动更新也就是low和high的更新,如果我们查找完一圈,没有对low和high加 1 操作,会出现什么情况呢?同样下边留言,亲自实践,给出截图正确答案者,发红包一个。

五、二分的三个适用条件

5.1 二分必须是顺序结构

我们前边学顺序结构的有顺序栈和顺序队列,其实它们的底层实现都是借助数组,所以所谓的顺序结构就是数组的实现。

我们要思考一个问题,为什么非要借助数组而不是链表呢?嗯,想起来了,数组的优点是什么?你能想到吧,咱们之前的文章也写的非常详细,那就是随机访问的时间复杂度为 O(1)。而链表却不是,所以这就是我们借助顺序结构的原因,这样二分查找更快。

思考:如果我们在链表上添加索引,实现二分查找,会不会是另外一番景象?提示一下,可以了解一下跳表,就是借助单链表加索引实现的。

5.2 数据必须有序的

为什么数据是有序的?我们想想如果数据无序的话,那大小关系就乱了,而且在得知中位数与查找的数据大小关系时,其他数据是乱的,所以无序的数据对于二分查找是不适用的。

5.3 数据量不能太大也不能太小

文章开头我们从 10 个数据中查找一个数据,我们直接遍历就可以了,这是数据量小的情况下。

如果数据量很大,我们想一下,我们是基于数组实现二分查找的,数组的一个特点是什么,内存空间是连续的,所以说数据量太大,在内存中开辟连续的内存空间很吃力的。所以太大的数据量也不适合二分查找。

5.4 小结

做个小结,今天主要分享了二分查找的思想以及应用,还有二分查找使用中应注意的地方,后边对于什么情况下适用于二分查找,什么情况不适合于二分查找,原因是什么这都是重点,都要去掌握。

今天分享的二叉树是没有重复数据的,如果有重复数据我们该怎么解决?会在下一篇具体的进行讲解。

对于海量数据查找还有一些其他的数据结构,比如散列表、二叉树等,这个不急,咱们慢慢的更新,先把最基本的学好,其他就很好学了。


❤️ 不要忘记留下你学习的脚印 [点赞 + 收藏 + 评论]

本文首发于原创公众号: 小鹿动画学编程。第一时间更新哦!


作者Info:

【作者】:小鹿

【原创公众号】:小鹿动画学编程。

【简介】:和小鹿同学一起用动画的方式从零基础学编程,将 Web前端领域、数据结构与算法、网络原理等通俗易懂的呈献给小伙伴。先定个小目标,原创 1000 篇的动画技术文章,和各位小伙伴共同努力一起学习!公众号回复 “资料” 送一从零自学资料大礼包!

【转载说明】:转载请说明出处,谢谢合作!~