粗析二分查找 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
二进制状态转移的最小覆盖问题

粗析二分查找

daybreakcx posted @ 2009年3月17日 00:34 in 算法 , 2123 阅读

一、简介

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

对于一串数:

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,只是我不知道罢了(有点驼鸟-_-!)。

二、最原始的二分查找

回到我们的话题,我们先将最简单的二分查找,最简单的二分查找当然是判定一个数是否在给定序列中(查找嘛!),那么我们有如下程序:

bool BinarySearch(int f,int t,int target,int* a)
//f代表其实下表,t代表终止下表,target代表要找数值,a表示有序列表数组,用整数方便说明
{
        int mid;
        while (f<=t)
        {
                mid=f+((t-f)>>1);//取中间位置
                if (a[mid]==target) return true;//找到直接返回
                else if (a[mid]<target) f=mid+1;//目标在mid左侧
                else t=mid-1;//目标在mid右侧
        }
        return false;//肯定不存在了
}

 

看这段程序,注意几点:

 

首先,条件是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出现的位置,于是乎我们有如下程序: 

int BinarySearchLower(int f,int t,bool* a)
//f表示其实下标,t表示终止下标
{
        int mid;
        while (f<t)
        {
                mid=f+((t-f)>>1);//取中间位置
                if (a[mid]) t=mid;//中间为true,丢弃mid右边的true
                else f=mid+1;//中间为false,丢弃mid及其左边的false
        }
        if (!a[f]) return -1;//不存在
        else return f;//坐标最小满足条件的位置
}

 

这里发现缩减区间的双方不平衡(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!

问题出在哪里呢,先给出我的代码:

int BinarySearchUpper(int f,int t,bool* a)
{
        int mid;
        while (f<t)
        {
                mid=f+((t-f+1)>>1);//取中间坐标,这里是唯一的不同
                if (a[mid]) t=mid-1;//a[mid]为真,我们删除mid以及其右边的一半
                else f=mid;//a[mid]为假,我们删除mid左边的一半
        }
        if (a[f]) return -1;//没找到
        else return f;//找到返回下标
}

发现问题所在没?就是那个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=x3-5x2+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. 文章下面没有了,但是不得不说:“我还有”!

 

DesertedCastle 说:
2012年5月14日 15:43

剖析的真透彻,谢谢博主解惑!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter