Binary Search

这是一个很著名的算法,就是二分搜索,一般可以在算法和数据结构中都能见到这个名字的存在。今天讲这个话题是因为前几个星期看C语言的时候,又再次看到这个算法,想起以前在数据结构学的知识,觉得这个算法真是大有文章,比较好玩。

二分搜索的思想很简单,在一个已经排好序的数列里找一个数,那么每次找中间那个比一比,如果要找的数比中间大,那么要找的数肯定在原来数列的后半部分了,反之亦然。按照这个思想做下去,一般很快就能找到那个数。现实中也有这样的例子,比如猜数字的游戏,一般也喜欢猜中间那个,然后就可以在几个回合之内猜到数字。

刚才是通俗的说法,一般来说,算法中的二分搜索要求如果原来数列有,则返回序号或指针,如果该数不存在,则返回不存在。刚才的通俗说法还有一个地方没说清楚,就是那个“比一比”。现实中,我们可以一眼可以看出大还是小,但在计算机中,要知道A是大于、等于还是小于B,要比较两次。下面给出其中一种解法的部分代码。
while (low <= high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else
return mid;
}
return -1;

这是一种正确的写法,可见在while循环内就完成搜索的过程。这个版本叫做Recognizing Equality,就是每次二分的时候如果刚好和中间的数相等,就直接结束。这是最容易理解的一种写法。

还有一种写法,没那么直接,叫Forgetful Version,就是每次不去特意比较中间的数,让循环一直下去,因为最后范围会收敛到只有一个数,所以也能完成任务,代码如下。
while (low < high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid;
else
low = mid + 1;
}
if (v[low] == x)
return low;
else
return -1;

这种写法的好处是每个循环里只需要比较一次,但是不是比较的次数是不是一定比第一种少呢,这不一定,因为第一种写法可以提前结束,第二种写法一定要收敛到范围只有一个数才结束循环。那到底哪种写法比较次数少呢?解答这个问题前,最好先搞清楚影响这两种写法的关键因素是不是比较的次数,书上说是的,到底是不是可以想一想汇编。

哪种写法的比较次数少,有一种分析方法叫比较树,把每次的比较用圆圈标出,下图是第二种写法的比较树(部分)。同样道理可以画出第一种写法的比较树。

Binary Search

可以数出来,当数列长度是10的时候,第二种解法的比较次数无论是存在还是不存在的树,都是4.4次。但是第一种解法的成功搜索的比较次数要4.8次,假如该数不存在,平均要比较7.1次。

不过虽然第一种写法每个循环要比较两次,但是两次比较其实有关联的,都是和同一个数比较,因此两次比较加起来的时间和只比第二种写法的一次比较的时间稍多一点,完全不是我们所想象的两倍时间,因此可能第一种写法的效率还是比第二种高。

但是,第一种写法有一个最致命的弱点,就是处理有相同的数的时候,比如“1,2,2,2,5”五个数,我现在搜索2,算法找到中间那个,发现相等,没有继续比较,所以返回的序号是2(假设从0开始)。这样就要命了,也就是说算法无法确定返回的是哪一个,这就很难做到通用性。相反第二种,它把大于等于归为右半部分,于是有相同的数的时候总是可以返回第一个,或者如果把把等于归为左半部分,就总能返回相同数中的最后一个。因此,大部分通用算法的写法,比如C+=的STL,应该也是用第二种的。我个人也喜欢第二种写法。

Advertisements