从零开始学算法:4.二分查找

作者: | 更新日期:

看完是不是发现二分查找竟然如此简单?

这篇文章涉及的源代码可以全部免费获得,在公众号中回复“二分查找”可以获得。

一、背景

大家好,我是tiankonguse。
由于某些原因,经常有人想学习算法但之前又没有相关经验,不知道从何做起。
我思考了许久,计划写一个系列来分享如何入门学习算法。

之前已经分享了《认识算法》、《了解套路长啥样》、《排序算法》,这是第四篇。
本来还不知道分享什么。工作中别人交接给我了一个项目,简单看之后发现二分查找算法竟然写错了,虽然没有死循环,但是查找的定义不明确(有时候返回大于的值,有时候返回小于的值)。
这篇文章就分享一下二分查找吧。

二、基本知识

二分查找是一个很常见的算法,主要用来在有序的数组中查找指定值的位置。
这个特定的含义不仅仅是等于,还可以是第一个大于和第一个大于等于的位置。

以数字为例,具体问题就是:
1.指定数字的位置?
2.首个大于等于指定数字的位置?
3.首个大于指定数字的位置?
4.最后一个小于指定数字的位置?
5.其他情况

正常情况下,我们可以通过遍历有序数组来做到这些,不过他们的复杂度将会是O(n)。
而二分查找的思路是不断的计算一个中间节点,通过判断中间阶段快速将查询空间减半。

下面以增序数组为例,分别来看看各种情况吧。

三、查找数字的位置

对于精确查找位置这个,可能会面临几种情况:1.不存在,2.存在一个,3.存在多个。
所以问题又转化为了查找数字首次出现的位置 和 最后一个出现的位置。

先来看看首次出现的位置的代码吧。

我们可以定义left和right是全闭合的区间,这样就可以精确的控制left和right的位置了。
如果mid小于value,可以确定答案肯定不在[left, mid],所以我们应该去[mid+1, right]查找。
如果mid大于value,可以确定答案肯定不在[mid, right],所以我们应该去[left, mid-1]去查找。
如果mid与value相等,我们就不好确定子区间如何划分了。

不过还好,一般情况下 mid < right 的(思考题1:为什么),所以我们可以大胆的把right设置为mid,使得区间范围继续变小。 只有一种情况下 mid 等于right,那就是 left 也等于 right,此时已经找到答案了。

而对于查找最后一次出现的位置这个问题,只需要修改上图的一行代码即可(思考题2:怎么修改)。

四、查找首个大于等于指定数字的位置

上面讲的是等于的情况,对于不存在的返回了-1。
而对于大于等于的情况,其实会发现更简单,不信看代码,和等于的少了几行代码。
由于太简单了,是不是都没啥说的了。

五、查找首个大于指定数字的位置

对于首个大于的数字的位置,你看完下面的代码肯定会惊呆的。
再给你们出个问题吧,这个代码与查找首个大于等于的代码有什么区别呢(思考题3)?

六、最后一个小于指定数字的位置

前面的两个例子是首个小于和首个小于等于的,并且两个代码极为相似。
所以这里只展示一下最后一个小于的代码,而对于最后一个小于等于的,留作思考题,大家来思考下差异在哪里(思考题4)。

对于最后一个小于的查询,我们对区间的定义稍微变化一下,这里改为右边是开区间。
改之后,你会发现代码和上面的代码几乎一样。
这里再出一道思考题,如果这里使用闭区间会有什么问题,该如何解决呢(思考题5)?

七、其他查找情况

首个等于、最后一个等于、首个大于、首个大于等于 这四种情况看完了,其他的情况其实都是变种,不过对于 最后一个小于 我还是简单介绍了。

下面来看看其他情况吧。
对于首个小于 或 首个小于等于的查找,直接比较第一个即可。
对于最后一个大于 或 最后一个大于等于的查找,直接比较最后一个即可。
对于最后一个小于的查找,等价于首个大于等于的位置减1,当然不存在的需要特殊判断(第六小节讲解了)。
对于最后一个小于等于的查找,等价于首个大于的位置减1,不存在的特殊判断即可(第六小节修改一个地方)。

这样我们就把增序的所有情况都分析完了。
回头再看看上面的几个代码,可以发现除了查找等于的有点特殊,其他的都类似,模板如下:

总结一下就是这样:
查询首个或最后一个XX的问题,也就是查询满足需求的最小或最大位置问题。
根据 mid 不满足需求的情况,我们可以直接确定其中边界。
而对其其他的情况,我们需要判断是否得到答案,没得到则确定另一个边界。

八、尾语

看完上面我整理的模板,是不是发现二分查找竟然如此简单?

不过有一点我还是需要强调一下。
对于首个相关的查找,我们使用的右闭区间。
而对于最后一个相关的查找,我们使用的是右开区间。
这样做得目的是使得所有的查询都最简单。

当然所有地方都使用右闭区间 或 右开区间 也没问题。
但是需要多考虑几种情况,恰恰是这些情况,很多人考虑不充足导致二分查找死循环。
另外有人可能发现了死循环,会加更多的特殊判断,这样虽然不会死循环了,但是可能导致二分查找的定义不明确。
死循环和定义不明确是二分查找最常见的问题,希望大家尽量能够避免。

最后,上面给大家出的思考题希望大家也想想。
这篇文章涉及的源代码可以全部免费获得,在公众号中回复“二分查找”可以获得。


本文首发于公众号:天空的代码世界,微信号:tiankonguse-code。

推荐阅读:

今天长按识别上面的二维码,在公众号中回复“ACM模板”,你将免费获得我大学耗时四年整理的《ACM算法模板》。
回复“算法的世界”,或点击阅读原文加入“tiankonguse的朋友们”,已有三百多个小伙伴加入。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越