那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

把二分查找算法写正确需要注意的地方

今天再次解决一个需要使用二分查找的问题,再一次的,我又没有一次过写对.(为什么我说"又"?)

抓狂了,似乎开始有一些"二分查找恐惧症".

为了以后能够一次将这个基本的算法写对,我决定再仔细研究一下.我之前有写过一个二分查找的算法,在这里,这一次再以这个问题为例来说明.

我今早写下的错误代码类似于下面的样子:
#include <stdio.h>

int search(int array[], int n, int v)
{
    
int left, right, middle;

    left 
= 0, right = n;

    
while (left < right)
    {
        middle 
= (left + right) / 2;
        
if (array[middle] > v)
        {
            right 
= middle - 1;
        }
        
else if (array[middle] < v)
        {
            left 
= middle + 1;
        }
        
else
        {
            
return middle;
        }
    }

    
return -1;
}

int main()
{
    
int array[] = {012345671319};

    
int m = search(array, sizeof(array)/sizeof(array[0]), 1);

    printf(
"m = %d\n", m);

    
return 0;
}

实际上,如果使用测试用例来测试,这个算法并不是在所有情况下都会出错的,还是有时可以得到正确的结果的.但是,你能看出来它错在哪儿吗?

在这里,循环的开始处,把循环遍历的序列区间是这样的:
left =0, right = n;
while (left < right)
{
    
// 循环体
}
也就是说,这是一个左闭右开的区间:[0, n).

但是,在循环内部, 却不是这样操作的:
        middle = (left + right) / 2;

        
if (array[middle] > v)
        {
            right 
= middle - 1;
        }
        
else if (array[middle] < v)
        {
            left 
= middle + 1;
        }
        
else
        {
            
return middle;
        }
当array[middle] > v条件满足时, 此时v如果存在的话必然在左闭右开区间[left, middle)中, 因此,当这个条件满足时, right应该为middle, 而在这里, right赋值为middle - 1了, 那么, 就有可能遗漏array[middle - 1] = v的情况.

因此,这种错误的写法并不是在所有的情况下都会出错,有时还是可以找到正确的结果的.

这是一种典型的二分查找算法写错的情况,循环体是左闭右开区间,而循环体内部却是采用左闭右闭区间的算法进行操作.
下面给出的两种正确的算法,算法search是左闭右闭区间算法,而算法search2是左闭右开区间算法,可以对比一下差异.
int search(int array[], int n, int v)
{
    
int left, right, middle;

    left 
= 0, right = n - 1;

    
while (left <= right)
    {
        middle 
= (left + right) / 2;
        
if (array[middle] > v)
        {
            right 
= middle - 1;
        }
        
else if (array[middle] < v)
        {
            left 
= middle + 1;
        }
        
else
        {
            
return middle;
        }
    }

    
return -1;
}

int search2(int array[], int n, int v)
{
    
int left, right, middle;

    left 
= 0, right = n;

    
while (left < right)
    {
        middle 
= (left + right) / 2;

        
if (array[middle] > v)
        {
            right 
= middle;
        }
        
else if (array[middle] < v)
        {
            left 
= middle + 1;
        }
        
else
        {
            
return middle;
        }
    }

    
return -1;
}

下面再给出另一种典型的错误的二分查找算法,当查找的元素不在序列内时,它可能造成程序的死循环.
int search(int array[], int n, int v)
{
    
int left, right, middle;

    left 
= 0, right = n - 1;

    
while (left <= right)
    {
        middle 
= (left + right) / 2;
        
if (array[middle] > v)
        {
            right 
= middle;
        }
        
else if (array[middle] < v)
        {
            left 
= middle;
        }
        
else
        {
            
return middle;
        }
    }

    
return -1;
}
为什么会造成死循环?

从循环条件来看,这个算法的操作区间是左闭右闭区间的,因此当array[middle] > v时,v如果存在的话应该在[left, middle- 1]中,因此此时right应该是middle - 1,而不是middle;类似的,当array[middle] < v时,下一次操作的区间应该是[middle + 1, right]中.而当元素不存在这个序列中时,算法在一个错误的区间中循环,但是又不能终止循环,于是就造成了死循环.

因此,要将二分查找算法写对,其实很多人都大概知道思想,具体到编码的时候,就会被这些看似微小的地方搞糊涂.因此,需要注意这一点:
算法所操作的区间,是左闭右开区间,还是左闭右闭区间,这个区间,需要在循环初始化,循环体是否终止的判断中,以及每次修改left,right区间值这三个地方保持一致,否则就可能出错.



posted on 2009-09-21 23:46 那谁 阅读(11076) 评论(29)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

因为二分查找的思想很简单, 很多人稍微看看就开始编码了, 没有考虑:
1. 每次递归中,区间如何划分
2. 递归的边界有哪些,是否能达到
3. 查找的值存在多个时, 将取得哪一个

仔细推敲边界的人不多。 大多都是随手写写, 最多加几个测试数据。
区间划分, 我只在少数几个地方看到是被“二分”, 普遍做法是“三分”。
少数几个地方是《代码之美》;cplusplus网站中lower_bound,upper_bound的伪代码。
讨论多值取向的文章就更少了。
2009-09-22 00:04 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
汗,你回复的真快....
2009-09-22 00:07 | 那谁

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@那谁
cpp的rss比较快。。。


这里有一份代码:
http://www.cnblogs.com/Devfly/archive/2009/09/18/can-you-write-a-right-binary-search-algorithm.html#1651172

是将闭区间[lower,upper], 取m = (lower + upper)/2
分为2个区间[lower,m] ; [m+1,upper]

递归边界是区间只含一个元素: [lower,lower]

取向是返回[lower,upper]中大于等于target的index。
递归边界一定能达到很好证明, 取向比较麻烦。


而其他一些常见的区间取法, 比如[first,last),
还有中值的取法,比如 (lower + upper + 1)/2, 或者用那个什么黄金分割……
以及多值时的取向, 随机, 第1个, 最后1个。
它们与stl中lower_bound, upper_bound的关系
等等…… 都挺有意思的……
不过最近有其他事要忙…… 只好终止了……

你感兴趣的话可以研究研究, 我就直接捡个现成了~~~
2009-09-22 00:25 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

编程珠玑上面专门有一章讲这个,呵呵。
另外wiki页面上提到一点,three-way/two-way比较的区别,个人感觉正是two-way比较造成了区间划分和边界设定容易混乱。不过three-way也一样。比较欣赏stl里面lower和upper的写法。
另外那个多值取向的问题确实折腾了我好久,也没什么很优雅的解决办法。
2009-09-22 05:58 | 唐僧

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
大多数情况下,如果存在多值的话,一般取哪个都是无所谓的。
2009-09-22 11:12 | 陈梓瀚(vczh)

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
编程珠玑上有讲这个? 第2版中? 第1版已出版很久、很多细节记不清了……
wiki是指编程编程珠玑的wiki? 给个链接撒~~~

我第1次发现这个问题是在看《代码之美》时,当时困惑了很久“难道我以前不是这样写的?”。我的确是写成three-way了。
确实, 如果three-way是听说二分查找思想后,就能立即编码的话, two-way就需要深入考究考究才能编写出来。


two-way就能有明确的取向啊。
对区间[lower,upper]:
1. 如果取中值 m = (lower+upper)/2
将区间划分为[lower,m],[m+1,upper]
直到区间只有一个元素:[lower,lower]
取向就是从lower到upper, 第1个大于等于target的index。

2. 如果取中值 m = (lower+upper+1)/2
将区间划分为[lower,m-1],[m,upper]
直到区间只有一个元素:[lower,lower]
取向就是从upper到lower,第1个小于等于target的index。

上面给出了一份代码的链接, 我觉得挺优雅的……
2009-09-22 14:48 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@陈梓瀚(vczh)
存在相同键的有序序列中,查找取向是有用的。
它能解决:“找键等于k的所有值”,“找键大于等于p,小于等于q的所有值”, 这种常见的需求。
2009-09-22 14:51 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
编程珠玑里面确实有一章讲解算法正确性的,是以二分查找算法来讲解的.
2009-09-22 15:07 | 那谁

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
看了你给的帖子,感觉我的算法还有问题,就是在存在多个相同元素的时候没有返回第一个元素.回头再研究一下了,目前至少算法是"正确的",只是不够"精确",哈哈.


2009-09-22 15:13 | 那谁

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@那谁
第2版还是第1版的编程珠玑? 书中有证明取向性么?
取向其实也只算个附加需求。 只对多值才有用……

我不知道three-way如何写出固定取向……
只考虑过two-way的几种区间划分的取向。
期待你的研究成果~~~

2009-09-22 15:21 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
我看的是这本编程珠玑:
http://www.douban.com/subject/3227098/
2009-09-22 15:32 | 那谁

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
这种情况下应该用具有多重值的map,怎么能给列表增加太多负担
2009-09-22 17:33 | 陈梓瀚(vczh)

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@陈梓瀚(vczh)
你再次偏题。怎么又扯上列表了?

多重值的map? 比如std::multimap?
如果使用的是std::multimap, 我相信用得更多的也是lower_bound、upper_bound、equal_range, 而不是find。
同样说明了对存在相等键的序列,查找的取向是有用的。


如果需要一个仅仅构建一次,查找多次,并且含有等值键的序列,并不一定需要multimap。
std::lower_bound,std::upper_bound同样可以对数组或者list查找,仅仅需要序列有序,并不要求序列有其他什么特性, 列表的负担又从何说起?


如果待查找的序列有相等的键, 那么查找算法有一定的取向就是一个有用的需求。跟序列是array、list还是map无关。

2009-09-22 17:53 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
是编程珠玑的第二版,http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html 这个链接是目录,以二分为例讲的,writing correct programs。ps, 这本书的影印版有卖的。我手上有一本,晚上回去翻看下,忘记有没有关于取向性的证明了。
wiki我没说清楚,是二分查找的wiki页面。2-way和3-way的讨论在Syntax difficulties章节里面 http://en.wikipedia.org/wiki/Binary_search#Syntax_difficulties

@陈梓瀚(vczh)
array list map 不影响搜索算法的本质,只是外壳不同罢了。
如果要搜索的是某个子区间而不是单一值的话,考虑多值取向就很有必要了。

@那谁
我见过的能够熟练而准确的写出二分的人都是在高中时候经历过系统oi训练的,呵呵。期待你的3-way研究,原文的代码在大多数情况下已经够用了,呵呵。
2009-09-22 20:21 | 唐僧

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
谢谢~~

我想到一个证明3-way不可能实现确定取向的方法。 其实非常简单……

因为一个binary-search算法,必须对所有输入数据都有确定的取向,才能说该算法有确定取向。
故证明某个binary-search算法不具有确定取向只要构造出一个反例,即可……

比如…… 一个极端的数据:键全部相同。 3-way肯定是第1次就退出查找了, 肯定不具有确定取向了。

2009-09-22 20:43 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
多谢指点,下午我隐约思考的方向出了问题,果不其然,惯性思维的力量啊。

另外,我去翻了The art of computer programming,发现了更好的解决办法。
那谁指出的两个错误都是源自 二分前的中值middle 和 二分后的区间边界bound 的冲突,而考虑到每次二分后的两个区间,不管二分前元素个数是奇数还是偶数,二分后的两个区间长度最多相差一,于是可以选择一个“近似”的中值middle,这个值紧靠较小区间的外侧即可。
Knuth命名这种算法叫Uniform binary search,在wiki页面有c实现。中文环境没有搜索到相关的讨论。 http://en.wikipedia.org/wiki/Uniform_binary_search
写这样的代码难度比一般的二分要大,感觉理解透了应该是最不容易出错的一种写法。
2009-09-23 04:58 | 唐僧

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
4点58分的回复……

The art of computer programming …… 一直没下决心去啃……

这个Uniform binary search是不是将除法操作缓存一下?
其实聪明点的编译器同样可以将
i /= 2u; 优化成 shr i
它使用一个预先计算好的middle值的缓存, 即使真能提高一点速度, 但能处理这种情况吗?
int a[] = { 7, 3, 5, 7, 2 }; 整个a无序, 但a[1] - a[3]升序。
binary_search(keys=a, target=5, lower=1,upper=3 );


确实two-way不好写。 12点多的时候就去问了一个拿过2次ACM金牌的室友,让他写一个二分搜索。
他回答“让我想一想”时, 我还有点惊喜 —— 之前我也问过一些人, 但终于有一个不是张口(随手)就给出代码的人了, 大牛果然不同凡响。
等了一会后, 得到一个3-way的……

打算将数据结构重新学一遍…… 透彻理解一下……
以前学的那叫啥…… 所以嘛, 只能看着室友拿金牌-_-。

2009-09-23 05:51 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧

哦 ……

int a[] = { 7, 3, 5, 7, 2 }; 用Uniform binary search可以如下处理……
binary_search(keys=a+1, target=5, count=3 );

快天亮了, 头有点晕……
2009-09-23 05:54 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
再回一贴 ……

Uniform binary search中需要的那个table —— delta, 好像可以用template meta programming在编译时计算完毕 ……
C++太强大了~_~

否则, 如果运行时计算的话:
1. 将make_delta的工作留给client(就像链接中的示例代码一样)
会使得unisearch不太好用。多次调用make_delta虽然不会错, 但赔本了。
如果只调用一次, 时机不好掌握。
如果在main中, main前的执行代码不能使用unisearch, 而且如果每个库都要求在main中这么初始化一次, main会受不了的……

2. unisearch自己处理好make_delta
那每次对unisearch的调用,会有一次额外的运行时检测 if (!is_init) 是逃不掉了。
2009-09-23 06:02 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

汗,你们俩晚上都不睡觉的吗,怎么回复时间都在凌晨....
2009-09-23 11:27 | 那谁

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

两位,似乎还有一个问题,考虑一个极端情况,假如一个序列中都是同样值的元素,而所需查找的就是这个元素,很显然,第一次查找就会找到了,但是找到的却是序列的中间元素.
2009-09-23 11:39 | 那谁

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@那谁
http://www.cppblog.com/converse/archive/2009/09/21/96893.aspx#96970
2009-09-23 14:51 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@那谁
那个凌晨的时间是我的夜晚,我是GMT+1。其他的回复都是在课间,我现在这课上的,一天7个小时,所以几乎没有白天的回复。

@OwnWaterloo
我对于TMP没有研究,呵呵,就等c++0x了。

delta数组是生成二分点用的,记录每次二分相对于上一次二分点的偏移,对于一个长度固定N的待搜索数组来说,delta[]是一样的。而且dleta[]中的元素至多有log(2,N)个,make_delta[]是在数组长度变化之后重新计算的。
比如wiki上的例子,N=10那么delta[]的前几项即5,3,1,第一次二分点是5,第二次就是5+3=8或者5-3=2,第三次是8+1或者8-1或者2+1或者2-1。
这个计算量并不大,而且我感觉这个算法的目的并不是通过缓存二分点而提高性能,从命名上看uniform的意义好像是寻求一种 形式上 的统一,或者说是让代码更优雅吧,同时避免普通二分搜索常见的边界和中点的混乱。
(我确实搜索到了有文章提及Uniform比普通二分更有效率,一篇讨论搜索算法耗能的,energy consomation,没有细看)
2009-09-23 22:45 | 唐僧

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
看来就我是夜猫了……
说点题外话……
因为上面给出的是递归代码, 所以就稍微查看了一下各种编译器的优化情况, 有点吃惊……
使用递归求阶乘的代码,msvc8,9; gcc 3.4.x可以优化为迭代,vc6不行。
对上面提到的二分搜索的递归形式:
tail_recursion

gcc也能将为递归优化为迭代。
下面是一个转化为迭代的版本:
iteration

gcc对这两者生成的代码,除了标号不同,其他地方完全一样……
msvc系列就不行了…… 老老实实的递归了……
 
2009-09-24 00:05 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
又一次证明了gcc的强大。我猜测gcc的编译过程中很可能用到了大量的模型匹配,能够解构复杂的递归过程,所以会比M$的效率更高。具体到编译算法上面我是一点都不知道。
如果是递归计算,如果不能很好的优化的话会消耗大量的栈资源,非计算目的的递归(我举不出合适的例子来)应该是无所谓的,gcc很可能也没有办法优化。
函数式编程应该是最合适于递归运算的。
ps,到这个地方已经彻底跑题了,呵呵。
2009-09-24 02:59 | 唐僧

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
gcc确实牛逼…… 怎么会有这种怪物……
对C/C++新标准支持很快……
compiler collection... 不知道它对非C/C++语言支持得怎样。
还支持这么多平台……


如果函数f返回前的最后一个步骤是调用另一个函数g,也就说g返回f后,f确实无事可做,再返回f的调用者;
那么,从理论上说,总是可以优化为:被调用函数g不再返回调用函数f,而直接返回f的调用者。
这样就可以在g中"复用"f的所使用栈资源。
这被称为尾调用。
http://en.wikipedia.org/wiki/Tail_call

如果尾调用恰好是调用的自身,就是尾递归(调用)。连使用的参数数量都是相同的…… 应该说是比较容易优化的。
并且,如果能将递归转换为尾递归形式, 通常"手动"转化为迭代形式就很简单了……


上面的递归代码符合尾调用。 我只是想验证一下是否真的会被编译器优化。
其实我预想是不行的,结果…… 还真的可以……
这样就有了一个理由:如果出于演示的目的,如果递归比迭代形式更优美,就不提供迭代形式了 —— 转迭代留作练习、或者换gcc ~_~
2009-09-24 03:47 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@OwnWaterloo
你真是夜猫子啊……
Knuth在书里给出了汇编的二分程序,你这么一说我又去看,估计就是gcc优化过的样子。因为是人写的程序,所以不存在call/ret,但是je/jne正好实现的是return condition ? recursion(para1) : recursion(para2) 的功能,区别仅仅在于对人来说跳转的地址是已知的,而对于计算机来说需要栈空间来临时存储。书里的汇编代码是基于Knuth的MIX构架的,不过跟x86的差不多,就是看着麻烦。
突然觉得那个尾调用异常强大,是不是理论上就可以支持无限深度的递归调用了?我印象中看编译原理的时候说call命令的结果是copy返回地址和局部变量到栈空间,那么共用参数的尾递归确实非常容易优化,无限深度就很容易被转成递推表达式了,呵呵。
2009-09-24 05:18 | 唐僧

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

@唐僧
高爷爷还用汇编实现算法的……
他别那么牛好不好……
 
我贴一下上面的c代码用gcc生成的汇编代码吧,不过是intel格式的,因为at&t格式的汇编我看不懂……
.globl _binary_search
    .def    _binary_search;    .scl    
2;    .type    32;    .endef
                               
_binary_search:               
    push    ebp                    
    mov    ebp, esp
    mov    edx, DWORD PTR [ebp
+16]     ;edx = lower
    push    esi                    
    mov    ecx, DWORD PTR [ebp
+20]     ;ecx = upper
    mov    esi, DWORD PTR [ebp
+8]      ;esi = keys
    push    ebx                     
    mov    ebx, DWORD PTR [ebp
+12]     ;ebx = target
    .p2align 
4,,15
L8:
    cmp    edx, ecx                    ;
if (lower!=upper)
    je    L2
L10:
    mov    eax, ecx                    ;middle 
= eax = ecx = upper
    sub    eax, edx                    ;eax 
-= edx, eax = upper-lower
    shr    eax                         ;eax 
/= 2
    add    eax, edx                    ;eax 
+= edx, eax = lower + (upper-lower)/2u
    cmp    DWORD PTR [esi
+eax*4], ebx  ;if (keys[middle] < target)
    jge    L3
    lea    edx, [eax
+1]                ;lower(edx) = middle(eax) + 1
    cmp    edx, ecx                    ;
if ( lower!=upper)
    jne    L10                         ;(keys,target,middle
+1,upper)
L2:
    pop    ebx
    mov    eax, edx                    ;
return lower
    pop    esi
    pop    ebp
    ret
    .p2align 
4,,7
L3:
    mov    ecx, eax                    ;upper(ecx)
=middle
    jmp    L8                          ;f(keys,targer,lower,middle)

迭代生成的汇编代码仅仅是标号取了不同的名字而已……
 
 
理论上是的, 因为理论上也可以转为迭代的吧。
实际上,写出为尾递归形式就是需要引入一些额外参数作为计算时的变量。
只要能写出尾递归形式,手动转迭代都不难了。
 
比如:
int factorial(int x) { return x>2? x*factorial(x-1): 1; }

不是一个尾递归, 因为factorial中对factorial调用后,需要取得结果并与x相乘才能返回。
 
转化为尾递归形式,需要引入一个额外参数:
int factorial_tail_recursion(int x,int acc) {
    
return x>2? factorial_tail_recursion(x-1,acc*x): acc;
}

int factorial(int x) { return factorial_tail_recursion(x,1); }

 

而factorial_tail_recursion“手动”转迭代都不是难事了:
int factorial_iteration(int x,int acc) {
    
while (x>2)
        acc 
*=x , --x;
    
return acc;
}
int factorial(int x) { return factorial_tail_recursion(x,1); }

再把2个函数合二为一, 始终以1作为累积的初始值:
int factorial_iteration_final(int x) {
    
int acc = 1;
    
while (x>2)
        acc 
*=x , --x;
    
return acc;
}

 
还是比较形式化的。 证明估计要留给vczh来做了。
2009-09-26 05:01 | OwnWaterloo

# re: 把二分查找算法写正确需要注意的地方  回复  更多评论   

建议参考这篇文章,http://blog.csdn.net/qiuqinjun/article/details/8976897,理解了循环不变式的话,远都不用怕写二分。
2014-01-28 09:04 | raywill

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理