粗析二分查找

一、简介

二分查找是一项程序员基本技能，基础，明了，他是基于一串可随机访问的序列的一种对数时间复杂度的查找方式，下面举一个例子：

对于一串数：

3        5        11        19        38        39        42

我们想要在7个数中查找11这个数值（当然不能说我看到了11在第三个位置），你可以这么问（注意这里是以升序为例）：

问：第4个数值是什么？

答：19

内心思维：19比11大，则11一定在第一个数值和第三个数值之中

问：第2个数值是什么？

答：5

内心思维：5比11小，那么11一定在第3个数值的位置

总结（很骄傲地）：我猜到了，11在第3个数值位

答（很激动）：恭喜你，答对了！

当然，你如果从最小的开始问或者是随机提问也能很快找到11（运气好的话），而且现代计算机运算速度很快，所以看不出有什么差别，但是如果数值个数急剧增长的话情况又是如何呢？二分查找的优势很明显！

举个简单的例子，如果你能将世界上65亿人口（我只是随便说说人数，大概在这个数量级）派个序（二分查找的前提条件），那么我告诉你我能在33次提问之内找到你要找的人！

就是如此的强大，就是如此的快速，但是问题在于——排序！

暂且不提排序，我们假设序列都是有序的（比如你拿到一张人口普查表，排号序的），那么这时候你就可以尽情显示你用二分查找找人的优势了（现实中也是如此，一般按名单用学号找人，都是先看一个学号判断他在哪个位置），工作交给计算机，编程则是程序员的事情，但是程序员知道了算法能轻松的写出来吗？

答案是大约只有10%的专业程序员才能正确的编写这个小程序！

不是我危言耸听，这句话引自《编程珠玑》，而且这本书还专门拿了一部分来讲二分查找。

细节决定一切，要想写出没有bug的二分查找不是简单的事情。当然，我也没说我是那10%，也就是下面的程序也可能存在bug，只是我不知道罢了（有点驼鸟-_-！）。

二、最原始的二分查找

回到我们的话题，我们先将最简单的二分查找，最简单的二分查找当然是判定一个数是否在给定序列中（查找嘛！），那么我们有如下程序：

看这段程序，注意几点：

首先，条件是f<=t这里有等号，二分查找经常出现差1的问题（我们后面说），后面的代码是没有等号的，思路很明显，mid表示中间下表，如果target比中间值小，则要找的数在左边，否则在右边。

其次，这里语句mid=f+((t-f)>>1)为什么不用mid=(f+t)>>1呢？因为数值范围！谁也不能保证f+t没有超出int的范围，当然如果t-f超出了我也没办法（此时长度超过int能表示的范围真不知道这个内存怎么申请的），因此用起始下标加上偏移是个很好的选择！

最后，如果在循环内如果找不到target，那么就表示这个数值不存在了（因为[f,t]表示target可能存在的区间，如果当t<f也就是区间为空时，target必然不存在）。

三、第一种变形

那么问题就是这样？当然不是，还有变化，还有拓展——有相同元素的情况或者是找满足区间条件的第一个target

举例说明：

3        5        11        19        19        19        38        39        42

相同元素：我们要找第一个出现的19的位置

找满足区间条件的第一个target：找不小于35的第一个数值

那我们怎么办呢？还想上面的程序一样？当然不行！如果是相同元素还有可能（找到一个后往左边看有没有target存在，直到目标，但是此时复杂度是线性的，最坏情况是当序列前半部分都是你要的数值时，你需要完全遍历他们），可是这不是我们想要的。

那么怎么办呢？我们来考虑下面转换：

合并上述两种假设：找满足不小于target的最小位置！假设我们把满足要找的数值的条件当作一个bool表达式，也就是其值是true或者是false，那么我们假设一个元素打等于target时候定义为true，否则为false，我们为了更一般，以查找19为例，于是上述序列就转换为了

false        false        false        true        true        true        true        true        true

这样就变成了要找第一个true出现的位置，于是乎我们有如下程序： 

这里发现缩减区间的双方不平衡（t是mid，f是mid+1），其实很容易理解，具体见注释，我们来分析一下是否可能有死循环的情况（前面说的差1）

当还剩下很多没有确定的元素时候显然不会出现死循环，只有当t和f至多差2的时候才会出现，分别讨论：

f==t：此时就要跳出循环，因为不满足f<t，那么只要判断a[f]就可以了

t==f+2：此时mid就变为f+1，也就是确确实实的中间位置：f        mid        t，我们分情况，若a[mid]是false，此时f赋值为了mid+1，也就是t，这样就变成了f==t的情况，前面已经讨论过了；如果a[mid]是true，此时t变为了mid，也就是t==f+1，下一条一起讨论。

t==f+1：此时mid==f，如果a[mid]是true，t就复制为mid即f，变成f==t的情况，前面已经讨论过，可以正常结束；如果a[mid]是false，f就赋值成mid+1即t，也变成f==t的情况，也可正常退出。

综上所述，这个程序不会出现差1的死循环情况，我们可以放心用了（有bug你和我说一声，我再研究）。

四、第二种变形

当然现实并不是像我们想象的就这么简单，还有第第二种变形，当然也不是什么大变化，却可能导致我们的程序全线崩溃！

第二种变形是这样的：在第一种变形的基础上，我们要找为false的坐标最大的元素位置。

你可能想了，其实很简单，我们不是已经有了第一种变形的代码了吗，改改就得了，那你就错了，虽然开源收益最大的是那些懒惰的中国程序员，虽然他们长时间的“拿来”能顺利的完成任务，但是这里我们要对他们说no！

问题出在哪里呢，先给出我的代码：

发现问题所在没？就是那个mid的赋值，很多人也常常就是因为这个赋值而差1导致了死循环！

那么我们先来分析一下这个程序针对各种情况如何变坐标，和商议个情况一样，用t和f的差值不超过2的情况来分析

f==t：此时和上面的一样，直接退出，然后判断a[f]那个点

t==f+2：此时mid的值还是一样的，为f+1，也就是确确实实的中间位置：f        mid        t，如果a[mid]为true，那么t赋值为了mid-1，也就是f，就变成了f==t的情况，如上所示，正确结束；如果a[mid]为false，那么f赋值为了mid，就成了t==f+1的情况，下面讨论。

t==f+1：就是在这里发生了分歧，我们来看看mid的值有什么不同，用mid=f+((t-f)>>1)，mid为f，用mid=f+((t-f+1)>>1)，mid为f+1也就是t，那么我们来看看这个例子，如果我们让mid变为了f，碰到了a[mid]==false的情况会怎么样呢？执行f=mid也就是f没有变化！那么接下来的就是死循环！多可怕啊！同时就算运气好一点，a[mid]==true，这是t=mid-1执行后，t==f-1，跳是跳出循环了，但是看着不觉得变扭吗（t<f）？所以很失败！我们再来看看用mid=f+((t-f)>>1)，这时候mid是t，如果a[mid]==true，t变成了mid-1即f，f==t，我们讨论过了，正常，如果a[mid]==false，f赋值为mid就是t，f==t，也正常，打完收工！

五、小结

我们来看看这两种情况到底区别在哪里，从宏观上说（刚才分析f和t的具体情况就算微观吧^_^），一个是想往区间的左侧靠近（最靠左的true）而另一个则是想往区间的右侧靠近（最靠右的false），如果用一样的方法就可能出错，那么分析一下两种mid的赋值方法，我们发现不论哪种，对于区间内元素个数为奇数的情况（t-f+1为奇数），两种赋值方法总能取到中间的位置（不信你试试看），t-f为偶数，((t-f+1)>>1)==((t-f)>>1)；但是差异出现在元素个数为偶数的情况（t-f+1为偶数），这也是让人很难抉择的地方，两边数值一样多，你选那个点做中间呢？第一种情况mid=f+((t-f)>>1)，我们发现总是取左边的，而mid=f+((t-f+1)>>1)，总是取右边的。

我们的程序不想最原始的情况（mid位置不是要找的就不算入查找范围：f=mid+1与t=mid-1），因此有上面几种操作差异，看第一种变形的程序，如果mid位置可行则取其以及其左侧，不可行就取其右侧（不包含其本身），这样就适应于偏左的赋值（如果行就把整个左半边包入，否则包入整个右半边）；而第二种情况则相反，因为当a[mid]为true的时候是取其左侧（不包含），a[mid]为false时候取其以及其右侧，所以选观测点应该在右半边的第一个！

六、其他变形

其他的变形就不是在这些细节上拓展了，而是另一个领域——实数。

在实数中常常有找一个逼近的过程，用的就是二分的思想，当然这个也是基于单调性的，比如我们要找y=x³-5x²+6x在(-1,0.5)内的实数根，我们发现这个函数在这个区间内是单调递增的，那么我们就可以用二分法逼近（此时复杂度不能用O(logn)来，n表示的是元素个数，而实数个数在区间内是无限的），程序很相像，原理也类似，就留给大家自己解决了，当然要注意一点的是不能用f<t这样的语句了，而是根据精度设定fabs(f-t)>PREC，其中PREC为你要的精度，这样不断缩小区间直到你满意为止(我是这么干的，大家别介意^_^）。

七、总结

不知不觉说了这么多，最后再多数几句。

1. 上面的程序可能有错误，希望大家以交流为主要目的有错直接提出，我会很乐意接受的^_^
2. 如果大家觉得用二分查找很容易错的话，有个方法可能能帮上你（我没这么干，只是有这个想法），把序列弄成树状的，抓取有序序列中间元素作为子树的根，这样就能保证这棵树的平衡了，当然这里要耗费建树的过程消耗和树内指针的内存消耗，不过不会有死循环等错误发生（遇到空节点就推出了） 。
3. 对于上面的true和false序列大家可以很容易改变到实际序列中，如要求大等于给定target的最小位置就可以用第一种变形令>=为true，改改条件而已，我就不再写出了，第二种变形对应的是小等于给定target的最大数值，当然大家喜欢的话可以把那个等于去掉，根据具体情况而定，逆序的序列也可以，反正具体要求不是我说的算的，模型是可以通用的。
4. 这篇文章算是一个观后感吧，我是看了《编程珠玑》一书和lovro的在topcoder上发表的Binary Search一文后根据自己的理解来写的，希望大牛们不要嘲笑我^_^
5. STL真是个强大的东西，什么都为用户考虑好了，里面关于二分查找的算法有四个：binary_search：在一个元素区段内找是否存在某个值；lower_bound：返回区段内元素出现的第一个位置，如果没有就返回假；upper_bound：返回区段内元素出现的最后一个位置，如果没有就返回假；equal_range：结合前面两者，返回等于给定值的迭代器区段。虽然功能齐全，但是个人认为自己动动手还是很开心的。
6. 关于二分查找的问题很多，我也曾经栽过跟头，比如当时去南京ACM的区域赛，热身时候来了个LIS，就因为二分爆掉了导致TLE（的最长递增子序列LIS有一个O(nlogn)的算法，很多人发过，有机会改天再讲吧），从此以后就有了阴影郁闷啊，痛下决心把这一切都弄懂。
7. 写下这篇文章发现is-programmer的博客真是好用啊，赞一个。
8. 文章下面没有了，但是不得不说：“我还有”！