那谁的技术博客

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

二分查找学习札记

我之前写过两篇关于二分查找算法的文章,这篇算是一个小结.我给这份文档整理了一份pdf格式的文档,可以在这里下载.


二分查找算法学习札记
说明
作者:那谁
blog: http://www.cppblog.com/converse
转载请注明出处.
二分查找算法基本思想
二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.

用伪代码来表示, 二分查找算法大致是这个样子的:
left = 0, right = n -1
while (left <= right)
    mid 
= (left + right) / 2
    
case
        x[mid] 
< t:    left = mid + 1;
        x[mid] 
= t:    p = mid; break;
        x[mid] 
> t:    right = mid -1;

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;
}


下面,讲讲在编写二分查找算法时可能出现的一些问题.

边界错误造成的问题
二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.比如下面就是错误的二分查找算法:
int search_bad(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;
}

这个算法的错误在于, 在循环初始化的时候,初始化right=n,也就是采用的是左闭右开区间,而当满足array[middle] > v的条件是, v如果存在的话应该在[left, middle)区间中,但是这里却把right赋值为middle - 1了,这样,如果恰巧middle-1就是查找的元素,那么就会找不到这个元素.
下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法,可以与上面的进行比较:
int search2(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 search3(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_bad2(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的时候,那么下一次查找的区间应该为[middle + 1, right], 而这里变成了[middle, right];当array[middle] < v的时候,那么下一次查找的区间应该为[left, middle - 1], 而这里变成了[left, middle].两个边界的选择都出现了问题, 因此,有可能出现某次查找时始终在这两个范围中轮换,造成了程序的死循环.

溢出
前面解决了边界选择时可能出现的问题, 下面来解决另一个问题,其实这个问题严格的说不属于算法问题,不过我注意到很多地方都没有提到,我觉得还是提一下比较好.
在循环体内,计算中间位置的时候,使用的是这个表达式:
middle = (left + right) / 2;

假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值.
所以,更稳妥的做法应该是这样的:
middle = left + (right - left) / 2;

更完善的算法
前面我们说了,给出的第一个算法是一个"正确"的程序, 但是还有一些小的问题.
首先, 如果序列中有多个相同的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比如考虑一种极端情况:序列中都只有一个相同的元素,那么去查找这个元素时,显然返回的是中间元素的位置.
其次, 前面给出的算法中,每次循环体中都有三次情况,两次比较,有没有办法减少比较的数量进一步的优化程序?
<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了修改:
int search4(int array[], int n, int v)
{
    
int left, right, middle;

    left 
= -1, right = n;

    
while (left + 1 != right)
    {
        middle 
= left + (right - left) / 2;

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

    
if (right >= n || array[right] != v)
    {
        right
= -1;
    }

    
return right;
}

这个算法是所有这里给出的算法中最完善的一个,正确,精确且效率高.
参考资料
1.<<编程珠玑>>
2.wiki上关于二分查找的说明:http://en.wikipedia.org/wiki/Binary_search




posted on 2009-10-05 21:53 那谁 阅读(14208) 评论(22)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 二分查找学习札记  回复  更多评论   

哈哈,这个总结真好~
2009-10-06 00:35 | 唐僧

# re: 二分查找学习札记  回复  更多评论   

orz..我就经常2分的时候orz
2009-10-06 12:08 | Vincent

# re: 二分查找学习札记  回复  更多评论   

再orz一个..第一次来到您的blog..超赞啊
2009-10-06 12:09 | Vincent

# re: 二分查找学习札记  回复  更多评论   

真这么神奇?我一直以为二分查找很简单啊!太打击我了!我简直是菜鸟中再也不能菜的了...........
2009-10-06 16:52 | 浮生如梦

# re: 二分查找学习札记  回复  更多评论   

受教了 O(∩_∩)O哈!
2009-10-07 08:19 | 迟到的爱

# re: 二分查找学习札记  回复  更多评论   

测试了下。。。。最后的代码效率不高。
2009-10-07 10:31 | 饭中淹

# re: 二分查找学习札记  回复  更多评论   

@饭中淹
哦?怎么测试的?
2009-10-07 10:59 | 那谁

# re: 二分查找学习札记  回复  更多评论   

@那谁
大量随机数值的查找。
用我自己的二分算法和最后的算法进行比较测试。

结果是最后的算法比我的算法慢个几百毫秒。

是10万int数组,1万预生成的待查数据。

重复1000次后得出的时间。
我的算法大概是1.8S
你文中的算法是2.XS
RELEASE版,在2.6GHZ的INTEL CPU上。

为了排除缓冲区干扰等,我用自己的算法的变种进行过测试,相差不到10毫秒。



2009-10-08 07:51 | 饭中淹

# re: 二分查找学习札记  回复  更多评论   

@饭中淹
可以把你的算法贴出来吗?
2009-10-08 10:09 | 那谁

# re: 二分查找学习札记  回复  更多评论   

@那谁
http://www.cppblog.com/johndragon/archive/2008/04/17/47345.html
在这里。
2009-10-08 14:58 | 饭中淹

# re: 二分查找学习札记  回复  更多评论   

@饭中淹
我这边测试的结果是我的稍好一些的,测试的数据是这样的:

#define LEN 400000

int main()
{
int array[LEN];
int i;

for (i = 0; i < LEN; ++i)
{
array[i] = i;
}

xbinary_search<int, int> search;

for (i = 0; i < LEN / 1000; ++i)
{
search.search_value(array, LEN, i * 10);
}
printf("done123\n");

return 0;
}
这个测试数据, 你的表现是0.176s,我的是0.047.

另外,你的代码在我的cygwin上面的g++上不能直接编译过去,我稍作了一些修改.
2009-10-08 15:51 | 那谁

# re: 二分查找学习札记  回复  更多评论   

@饭中淹
2-way和3-way的对比,通常和输入有关。
3-way一旦命中,就可以提前退出循环, 但每次循环要多一次compare。
2-way总是执行lgN次比较后才退出循环,再测试是否命中。
严格计算需要概率统计知识。
这种蛮力测试我也做过, 3-way通常表现得比2-way更优秀。


但2-way有一个决定性的优势,是3-way无法相比的。
"存在相同键的有序区间中查找键属于某个区间的所有值",对这种需求,2-way可以继续保持O(lgN)的复杂度, 而3-way会退化至O(N)。


stl中使用2-way而不是3-way,可能就是基于这种考虑吧 —— 即使在最坏情况下也要足够好, 在最好的情况也不算坏。
2009-10-08 16:23 | OwnWaterloo

# re: 二分查找学习札记  回复  更多评论   

@OwnWaterloo
是的,你这么分析有道理.所以最后的那个算法"精确"(都找到相同元素的第一个)的代价就是在一些情况下不如3-way高效.
2009-10-08 16:30 | 那谁

# re: 二分查找学习札记  回复  更多评论   

综上,我想这篇文章还需要做一些说明.稍后我会补充上,谢谢几位.
2009-10-08 16:35 | 那谁

# re: 二分查找学习札记  回复  更多评论   

好久没来了,貌似这回的论题是算法效率了。
2-way/3-way的二分算法都是基于无冗余的比较运算的,理论比较次数的下限不会达到log(2,n)。而
”3-way一旦命中,就可以提前退出循环, 但每次循环要多一次compare。
2-way总是执行lgN次比较后才退出循环,再测试是否命中。“
考虑到测试数据的生成方法,那么3-way的表现会好一些,结果就是大量的数据面前差距会被会放大。
但是如果附加大量无法命中的搜索,那么理论上二者差距会趋近于零。
我印象中数学方法分析算法效率的时候大概的过程是:写出汇编代码,看单次表现的指令数,数学求和。感觉不是很困难的事情,无非就是给一个所在位置n所需要搜索次数s的函数,对0..max求和看平均,但是运算量上看却是很麻烦的事情,特别是当这个函数比较复杂的时候。。

ps,在上次讨论的时候那个uniform二分的表现要好于3-way很多,我当时测了一万左右的数据,因为”动态“寻找二分点要比预先生成静态二分点多增加很多运算,而且这种增加是随着搜索空间的增大而增长的(这句话我不太确定,直觉上一倍左右的差距)。这也从另一方面说明了二分算法本身比较运算的运算量已经没有提高的空间了,优化仅仅是从周边入手,比如3-way的用一次比较的代价来减少循环的次数。

再ps,刚才写上一段的时候想起来通用指令集cpu的设计,尤其以intel为首,通过加长流水线,提高分支预测的效率来提高性能,一旦预测失败就会有比较大的性能损失。这和精简指令集的cpu的区别有点像3-way和2-way的区别,一个强调命中,一个强调稳定的结果。理念非常接近。
2009-10-09 08:11 | 唐僧

# re: 二分查找学习札记  回复  更多评论   

再补充一点,翻了一下编程艺术,mix结构上的汇编
3-way的每个循环的操作数大概是15个
uniform在12个左右
3个的差距在于取二分点的操作上面,占到了1/4。
没有2-way的实现,不过可以猜测每个循环的操作在13或者14个上。
那么这对于最终算法的影响确实是相当大的,因为纯粹用于比较两数大小的操作在一个循环中不过1/2左右。
2009-10-09 08:21 | 唐僧

# re: 二分查找学习札记  回复  更多评论   

@那谁
我是这样测试的,不知道有么有错。
第一步:将你的算法嵌入到我的binarysearch里面
static inline int _search( const T1 * pTArray, int nArraySize, const T2 & v, int & insertpoint )
{
if( pTArray == NULL )
{
insertpoint = 0;
return -1;
}

int left, right, middle;

left = -1, right = nArraySize;

while (left + 1 != right)
{
middle = left + (right-left) / 2;

if (_cmp( pTArray[middle], v ) < 0)
{
left = middle;
}
else
{
right = middle;
}
}

if (right >= nArraySize || _cmp( pTArray[right], v ) != 0)
{
right = -1;
}

return right;
//}

}
第二步:测试函数
#define MAX_DATA_COUNT 100000
int gDatas[MAX_DATA_COUNT];
#define MAX_FIND_DATA_COUNT 10000
int gFindDatas[MAX_FIND_DATA_COUNT];
#define MAX_TEST_TIMES 1000
void Test1()
{
typedef xbinary_search<int, int> INT_SEARCH;
for( int t = 0;t < MAX_TEST_TIMES; ++t )
{
for( int i = 0;i < MAX_FIND_DATA_COUNT; ++i )
{
int nPos = INT_SEARCH::search_value( gDatas, MAX_DATA_COUNT, gFindDatas[i] );
if( nPos != gFindDatas[i] )printf( "error !\n" );
}
}
}

void Test2()
{
typedef xbinary_search2<int, int> INT_SEARCH;
for( int t = 0;t < MAX_TEST_TIMES; ++t )
{
for( int i = 0;i < MAX_FIND_DATA_COUNT; ++i )
{
int nPos = INT_SEARCH::search_value( gDatas, MAX_DATA_COUNT, gFindDatas[i] );
if( nPos != gFindDatas[i] )printf( "error !\n" );
}
}
}

void Test3()
{
typedef xbinary_search3<int, int> INT_SEARCH;
for( int t = 0;t < MAX_TEST_TIMES; ++t )
{
for( int i = 0;i < MAX_FIND_DATA_COUNT; ++i )
{
int nPos = INT_SEARCH::search_value( gDatas, MAX_DATA_COUNT, gFindDatas[i] );
if( nPos != gFindDatas[i] )printf( "error !\n" );
}
}
}

xbinary_search3就是你的函数嵌入的

第三步:数据生成和测试代码
srand( 312431 );
for( int i = 0;i < MAX_DATA_COUNT; ++i )
{
gDatas[i] = i;
}

for( int i = 0;i < MAX_FIND_DATA_COUNT; ++i )
{
gFindDatas[i] = (rand() % 10000) * MAX_DATA_COUNT / 10000;
}
timeBeginPeriod(1);
DWORD dwT1 = timeGetTime();
Test1();
dwT1 = timeGetTime() - dwT1;
printf( "t1 = %u\n", dwT1 );
DWORD dwT2 = timeGetTime();
Test2();
dwT2 = timeGetTime() - dwT2;
printf( "t2 = %u\n", dwT2 );
DWORD dwT3 = timeGetTime();
Test3();
dwT3 = timeGetTime() - dwT3;
printf( "t3 = %u\n", dwT3 );
timeEndPeriod(1);

最后结果


t1 = 1828
t2 = 1822
t3 = 2155


2009-10-09 10:03 | 饭中淹

# re: 二分查找学习札记  回复  更多评论   

查找i*10的结果是:

t1 = 1159
t2 = 1160
t3 = 1515

你的算法的消耗时间仍然多几百毫秒

2009-10-09 10:07 | 饭中淹

# re: 二分查找学习札记  回复  更多评论   

@唐僧

对对,我忘了说了,如果查找目标不在区间中,2-way肯定比3-way高效。


-------- 关于 uniform --------
"因为”动态“寻找二分点要比预先生成静态二分点多增加很多运算,而且这种增加是随着搜索空间的增大而增长的(这句话我不太确定,直觉上一倍左右的差距)。"

上次我就说了嘛, 关于uniform这个词。
如果只从源代码(维基上的那份)入手uniform优化的实质就预处理一个delta,每次免去除法运算。
不管高爷爷是怎么一步一步想到这里来的(那本书我没看……), 源代码中已经不怎么能体现出来了。


但实际上,效果并不一定很显著, 我瞎猜的啊。
因为除数是2, 实际上并不需要做除法, 只是移位。

-------- 注意 --------
一次移位的写法有(但不限于)以下2种:
int m = lower + ( (upper - lower) >> 1);
int m = lower + (upper - lower) / 2u; /* 这个u很关键 */

第1种使用sar,第2种使用shr。 只要upper>=lower, sar,shr都是正确的。

而楼主和饭中淹使用的代码
int m = lower + (upper - lower) /2;
会被翻译为3条指令。
饭中淹的代码还没有考虑溢出的情况。

-------- 注意完毕 --------


那么,不使用uniform的方式, 每次计算middle的消耗就是:
减法,移位,加法。
lower, upper都是缓存在寄存器中的。
具体可以见上一篇文章的评论中我发的汇编代码。


而uniform的方式:
i += delta[++d];
大概就是
mov r1, delta[r2(d)*4+4]
add r3(i),r1

一次加法;一次内存访问;d需要多占用一个寄存器(否则更慢),++d还需要要一次加法。


这个静态存储区的内存访问很讨厌。
非uniform方式lower,upper所在页面肯定是被加载的,因为它们是函数参数,处在栈顶。
uniform的方式,delta就不一定在页面中,有可能被置换出去了。这种情况一旦发生,说不定效率就是数量级的下降,和非uniform完全没得比。
并且,这种情况,通过这种小的测试程序还不一定能测得出来 —— 怎么模拟一个大的、长期运行的、偶尔调用二分查找的程序,它已经将delta所在页面置换出去了?

从本质上来说, uniform的方式的一个直接缺陷就是造成数据的局部性不如非uniform的方式。而且这缺陷是无法修正的。 缺陷造成的影响可能会被uniform的其他优势所掩盖, 但缺陷始终存在。


当然, 上面全都是臆测,臆测。 需要实际测试一下。
我觉得只要非uniform的注意移位问题, 效率应该不会比uniform的差太多。即使不缺页,内存访问也是比较伤的。
一旦缺页,我觉得uniform就没什么可比性的了。



ps:
关于两种方式的对比:
1. 增加happy path的效率,不管unfortunate的效率
2. 兼顾所有情况的效率

除了uniform和非uniform,我还想起一个……
不知道hash表和红黑树算不算这种对比的例子之一……
2009-10-09 15:27 | OwnWaterloo

# re: 二分查找学习札记  回复  更多评论   

@OwnWaterloo
我确实理解错了,因为mix结构上不能实现右移这样的操作……所以有了uniform。
而且我也没有考虑到实际实际内存的分配情况。如果仔细考虑一下就能想到,这么多年来保持下来的,成为标准的,大量应用的是非uniform的二分,说明了实际应用要好的多。
stl里面的set/map都应该用的是红黑树吧,还有2-way的二分,都是兼顾所有情况的。hash表也挺极端,这个例子也挺像。呵呵,合适最好。先搞实现,在追求优化。
2009-10-09 22:37 | 唐僧

# re: 二分查找学习札记  回复  更多评论   

@唐僧

mix没有右移?
不过嘛…… 右移是除法的子集…… 没有也挺合理的…

嗯,在你介绍之前, 我完全不知道有uniform这回事……
高爷爷的书有时间一定得去看看……

sgi的stl中有非公开的红黑树实现。4中关联容器其实是红黑树的adapter...
就像std::stack,queue,priority_queue一样…… 尴尬……

我觉得吧,二分只要写正确就行了…… 复杂度肯定是lgN的。
lgN已经很猛了…… 常数稍微差点也坏不到哪去…… 优化是无底洞……
不记得在哪本书上看到过这么一句话"只需要让软件足够快"
2009-10-10 14:16 | OwnWaterloo

# re: 二分查找学习札记  回复  更多评论   

沒有一個人認真看樓主的貼的算法,search()和search_bad2()是一模一樣的錯誤算法,我跪了!!!
2013-04-08 10:21 | quatrejuin

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