内容简介：作者:看完是不是发现二分查找竟然如此简单？这篇文章涉及的源代码可以全部免费获得，在公众号中回复“二分查找”可以获得。
作者: tiankonguse | 更新日期:
看完是不是发现二分查找竟然如此简单？
这篇文章涉及的源代码可以全部免费获得，在公众号中回复“二分查找”可以获得。
一、背景
大家好，我是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的朋友们”，已有三百多个小伙伴加入。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
