vlambda博客
学习文章列表

大家好呀，我是 Rocky0429。

今天来讲二分查找呀，可能臭宝们觉得二分查找光看一下“二分”俩字就已经学会了了原理。

确实，二分查找的原理非常简单，但是往往越简单的东西越不容易掌握，不要把简单和容易画上等号。

尤其二分查找在解决实际问题时，要慎之又慎，在细节上稍不注意，臭宝们就可以给自己颁一个“ bug 制造机”的头衔。

至于是不是真的有这么邪乎，接着往下看就知道了。

   认识二分查找

二分查找，又叫折半查找，洋名儿 Binary Search。

二分查找的使用，要有一个前提条件：要查找的数必须在一个有序数组里。在这个前提下，取中间位置数作为比较对象：

• 若要查找的值和中间数相等，则查找成功。

• 若小于中间数，则在中间位置的左半区继续查找。

• 若大于中间数，则在中间位置的右半区继续查找。

不断重复上述过程，直到查找成功或者查找区域变为 0，查找失败。

二分查找在我们的生活中随处可见，比如写好一个 100 以内的正整数，臭宝们来猜我写的是哪一个，我只回答是大了还是小了。

傻瓜做法是一个个的猜，这就不说了。二分查找的话会像下面一样（部分）：

由于是 100 以内的正整数，按照二分查找规则，第 1 次先猜 50，如果我说大了，那第 2 次就猜 25，如果我说小了，那第 2 次就猜 75，以此往复。

假设要猜的数是 1，那么过程如下：

你看只花了 7 次就能找到，是不是很快，而且这还是在最坏情况下，也就是 100 个数的二分查找最多 7 次就能知道结果。

根据二分查找的思想，1000 个数的二分查找最多只需要查找 10 次，10000 以内的数最多只需要查找 14 次，有谁不相信可以自己动手试试，如果你不怕累的话。

下面我带臭宝手把手的复现一个二分查找。

从数组 10、11，21，32，53，85，138，223，361 中，查找是否存在值 21。

利用二分思想，设定 low 和 high 表示需要查找的区间的左右下标，mid 表示需要查找区间的中间元素下标。

过程如下图所示：

通过上面的讲解和例子相信你对二分查找的认识已经足够了，下面就是来看如何实现二分查找。

   二分查找常规实现

根据二分查找的思想，我们来看一下二分查找的常规实现。

def BinarySearch(arr, low, high, target): low, high = 0, len(arr) - 1
 while low <= high: mid = (low + high) / 2 if arr[mid] == target: # 找到 target return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1

这是一个最基本的二分查找的代码，是不是看着很简单？

很多臭宝们觉得看完了二分查找的思想，二分查找的代码也就直接出来了。

经验告诉我们，越简单的东西，越在细节上容易栽跟头，如果你现在拿起键盘准备疯狂输出不同意，那我还是建议你拿张纸出来，手写一个试试。

如果你写的丝毫不错，请在留言区告诉我，我要当你的舔狗。

刚刚是个小插曲，下面回到正题，我来详细说一下需要注意的点。

坑 1：while 循环退出条件

while 循环条件是 low <= high，不是 low < high。

为什么呢？我来详细讲一下。

首先我们要明确，当前这个二分查找，查找的是［low, high］区间，区间是左闭右闭区间，这一点很重要（二分查找的很多坑都是玩区间游戏）。

我们每次在查找区间中查找，找到目标值就停止：

if arr[mid] == target: return mid

或者查找区间变为 0，while 循环终止，查找失败。

如果 while 循环的条件是 low <= high，那循环终止条件相当于是 low = high + 1，此时区间是 [high+1, high]，肯定没有数大于一个大的数字，并且小于一个小的数字吧，那这就时查找的区间就变成了 0，while 循环终止。

那我们再来看 while 循环条件是 low < high，此时循环的终止条件相当于是 low = high，即此时的区间是 [high, high]。

这个时候查找的区间不为空，可以带个具体的数，比如 high = 5，此时区间是[5, 5]，有一个数 5，所以不为空。

但是这个时候 while 循环终止了，也就是区间 [5，5] 被强行扔掉了，万一找的这个 target 就是数组下标为 5 的那个数，这不 GG 了嘛。

坑 2：low 和 high 取值

我在代码里对 low 和 high 取值是这样的：

low = mid + 1high = mid - 1

有臭宝可能有为啥不是 “low = mid，high = mid” 的疑问。

还是那句话，我们在这查找的区间是 [low, high] 这种左闭右闭的区间，当发现下标为 mid 的数组元素不等于 target，那肯定下一步查找的是 [left, mid-1] 或者 [mid+1, right] 区间，因为刚刚下标为 mid 的元素已经比对过了，不需要再比对。

坑 3：mid 取值

mid 这个取值的话，一般不会有啥问题，基本都是下面这样：

 mid = (low + high) / 2

但是叭，我拿 Python 来说，Python 里整数值不受位数限制，正常来讲那就是它可以无限大，但是计算机毕竟有内存，你总得是有个限制。

加法这个叭，总归是不好控制，万一就有特别大的时候呢？

所以还是减起来舒服，所以碰到 low 或 high 特别大的时候，mid 可以取下面这样：

mid = low + (high - low) / 2

这二分查找的常规实现差不多就这些。

这个代码，一定要反复的看反复的记，最好能背下来。

对于数据结构和算法本身来说，理解它们的本质固然重要，但“背代码”同样也是必不可少的，很少有人在这上面下功夫。

可能很多人觉得“背代码”很可笑，拿“理解了就能写出来”举例，我感觉这倒不如是在纸上谈兵。

当年我在搞 ACM 的时候，对每种类型的题总是集中练，对每种类型有自己总结的模板，大量的练习和记忆，让代码形成肌肉记忆，要写的时候可以很快的写出来。

你想一下，如果这是在面试，那该是多大的优势。

   二分查找时间复杂度

首先我先来结果，二分查找的时间复杂度是 O(logn)。

这个怎么出来的呢？很好算。

一个数组长度为 n，以为二分查找每次查完，要查找的区间都会变成原来的一半，最坏情况下，一直到查找空间为 0 才停止。

所以它的查找区间会第 1 次是 n，第 2 次是 n/2，第 3 次是 (n/2)/2，假设循环 x 次，那公式变成：

即：

所以：

我在 【】中讲过，对于对数复杂度来说，不管你是以 2、3 为底，还是以 10 为底，通通记作 O(logn)。

至于为什么，忘记的，可以再回顾一下。

二分查找，到这基本就结束了。

总结来说呢，二分查找就是个事儿精，细节控，在用二分的时候一定要打起十二分精神。

上面的内容看懂了，基本二分就不会有太大的问题。

当然对于二分也不仅限于此，变形题还是不少的。这篇文章主要还是写的理想情况下的常规操作，实际情况下肯定不会说你数组单调无重复，当然作为初学者来说，现在的内容足够了。

能忍着看到这的都是真爱，记得点赞在看留言么么哒。

我是 Rocky0429，我们下次见。