动画：面试官问我如何在 1 亿数据中快速查找某一整数？(上)

写在前边

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

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

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

思维导图

什么是二分查找

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

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

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

动画实现

二分查找的性能

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

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

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

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

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

二分实现的三个重点

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

JavaScript 版本

PS：点击图片可以放大查看
Java 版本

PS：点击图片可以放大查看
C 语言版本

PS：点击图片可以放大查看
Python 版本

PS：点击图片可以放大查看

代码中有三个地方最容易出错。

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 个数据中查找一个数据，我们直接遍历就可以了，这是数据量小的情况下。

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

小结

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

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

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

文章中有两个地方需要自己去亲自动手实践，用你喜欢的语言去分析出现的问题，然后下方留言，并截图给小鹿，单独发两个红包，先到先得哦。

更多相关文章