二分查找算法在C/C++程序中的应用示例
二分查找算法的思想很简单，《编程珠玑》中的描述：在一个包含t的数组内，二分查找通过对范围的跟综来解决问题。开始时，范围就是整个数组。通过将范围中间的元素与t比较并丢弃一半范围，范围就被缩小。这个过程一直持续，直到在t被发现，或者那个能够包含t的范围已成为空。
DonaldKnuth在他的《SortingandSearching》一书中指出，尽管第一个二分查找算法早在1946年就被发表，但第一个没有bug的二分查找算法却是在12年后才被发表出来。其中常见的一个bug是对中间值下标的计算，如果写成(low+high)/2，当low+high很大时可能会溢出，从而导致数组访问出错。改进的方法是将计算方式写成如下形式：low+((high-low)>>1)即可。下面给出修改后的算法代码：
intbinarysearch1(inta[],intn,intx)
{
intl,u,m;
l=0;u=n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m;
elseif(x==a[m])
returnm;
else
l=m+1;
}
return-1;
}
这里注意一点，由于使用的是不对称区间，所以下标的调整看上去有点不规整。一个是u=m，另一个是l=m+1。其实很好理解，调整前区间的形式应该是[)的形式，如果中间值比查找值小，那么调整的是左边界，也就是闭的部分，所以加1；否则，调整是右边界，是开的部分，所以不用减1。调整后仍是[)的形式。当然也可以写成对称的形式。代码如下：
intbinarysearch1(inta[],intn,intx)
{
intl,u,m;
l=0;u=n-1;
while(l<=u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m-1;
elseif(x==a[m])
returnm;
else
l=m+1;
}
return-1;
}
这样也看上去比较规整，但是有个不足。如果想把程序改成“纯指针”的形式，就会有麻烦。修改成纯指针的代码如下：
intbinarysearch2(int*a,intn,intx)
{
int*l,*u,*m;
l=a;u=a+n-1;
while(l<=u)
{
m=l+((u-l)>>1);
if(x<*m)
u=m-1;
elseif(x==*m)
returnm-a;
else
l=m+1;
}
return-1;
}
当n为0时，会引用无效地址。而用非对称区间则不会有这个问题。代码如下：
intbinarysearch2(int*a,intn,intx)
{
int*l,*u,*m;
l=a;u=a+n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<*m)
u=m;
elseif(x==*m)
returnm-a;
else
l=m+1;
}
return-1;
}
上面给出的二分查找是迭代法实现，当然也可以用递归的方式实现。代码如下：
intbinarysearch3(inta[],intl,intu,intx)
intm=l+((u-l)>>1);
if(l<=u)
{
if(x<a[m])
returnbinarysearch3(a,l,m-1,x);
elseif(x==a[m])
returnm;
else
returnbinarysearch3(a,m+1,u,x);
}
return-1;
上述这些二分算法，若数组元素重复，返回的是重复元素的某一个元素。如果希望返回被查找元素第一次出现的位置，则需要修改代码。下面给出了一种解法：
intbinarysearch4(inta[],intn,intx)
{
intl,u,m;
intflag=-1;
l=0;u=n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m;
elseif(x==a[m])
flag=u=m;
else
l=m+1;
}
returnflag;
}
下面是《编程珠玑》上的解法：
intbinarysearch4(inta[],intn,intx)
{
intl,u,m;
l=-1;u=n;
while(l+1<u)
{
m=l+((u-l)>>1);
if(a[m]<x)
l=m;
else
u=m;
}
return(u>=n||a[u]!=x)?-1:u;
}
至此二分算法的代码讨论结束，下面讨论一下程序的测试问题。《代码之美》有一章专门介绍二分查找算法的测试，非常漂亮。这里班门弄斧，简单给出几个测试用例。针对binarysearch1。测试程序如下：
#include<iostream>
#include<cassert>
#include<algorithm>
#include<ctime>
usingnamespacestd;
intcalmid(intl,intu){returnl+((u-l)>>1);}
intbinarysearch1(inta[],intn,intx);
#definebs1binarysearch1
intmain()
{
longstart,end;
start=clock();
inta[9]={-2147483648,-13,-10,-5,-3,0,1,400,2147483647};
//中值下标计算的测试
assert(calmid(0,1)==0);
assert(calmid(0,2)==1);
assert(calmid(1000000,2000000)==1500000);
assert(calmid(2147483646,2147483647)==2147483646);
assert(calmid(2147483645,2147483647)==2147483646);
//冒烟测试
assert(bs1(a,9,0)==5);
assert(bs1(a,9,1)==6);
assert(bs1(a,9,2)==-1);
//边界测试
assert(bs1(a,0,1)==-1);//0个元素
assert(bs1(a,1,-2147483648)==0);//1个元素成功
assert(bs1(a,1,-2147483647)==-1);//1个元素失败
assert(bs1(a,9,-2147483648)==0);//首个元素
assert(bs1(a,9,-3)==4);//中间元素
assert(bs1(a,9,2147483647)==8);//末尾元素
//自动化测试
intb[10000];
inti,j;
for(i=0;i<10000;i++)
{
b[i]=i*10;
for(j=0;j<=i;j++)
{
assert(bs1(b,i+1,j*10)==j);
assert(bs1(b,i+1,j*10-5)==-1);
}
}
//自动化测试引入随机数
srand(time(0));
for(i=0;i<10000;i++)
{
b[i]=rand()%1000000;
sort(&b[0],&b[i]);
for(j=0;j<=i;j++)
{
intx=rand();
intk=bs1(b,i+1,x);
if(k!=-1)
assert(b[k]==x);
}
}
end=clock();
cout<<(end-start)/1000.0<<'s'<<endl;
return0;
}
注意到数组的元素有正数，负数，零，最大值，最小值。通常会忘掉负数的测试，引入最大值和最小值，主要是为了边界测试。
第一，测试了中值下标的计算。另外写了一个小函数，单独测试。考虑到内存可能放不下这么大的数组，因此只是模拟测试，并没有真正申请这么大的空间，但是对于中值下标的测试足够了。
第二，冒烟测试。即做一些最基本的测试。测试通过后进行边界测试。
第三，边界测试。这里有三种类型，一是针对数组元素个数，分别是0个，1个。二是针对元素位置，分别是首个元素，中间元素，末尾元素。三是针对元素值，有最大值，最小值，0等测试。
第四，自动化测试。这里自动生成测试的数组，然后针对每个元素进行成功查找测试。
第五，自动化测试，只不过数组的元素是随机值。
第五，性能测试。这里相关代码没有列出。以上测试都通过时，可以修改查找算法，添加性能测试的代码。其实可以简单添加一个比较的计数器。返回值从原来的查找结果改为比较的计数器值即可。代码比较简单，就不列了。
Note：二分查找容易忽略的一个bug
对于二分查找算法，相信大家肯定不会陌生。算法从一个排好序的数组中找指定的元素，如果找到了返回该元素在数组中的索引，否则返回-1。下面给出了解法。
//a为排好序的数组，n为数组的大小，x为指定元素
intbinarySearch(inta[],intn,intx)
{
intleft=0,right=n-1,middle=0;
inttmp=0;
while(left<=right)
{
middle=(left+right)/2;
tmp=a[middle];
if(x<tmp)right=middle-1;
elseif(x>tmp)left=middle+1;
elsereturnmiddle;
}
return-1;
}
乍看没有错误，但是不幸的是，该程序存在一个bug。当数组极大时，(left+right)可能为负数，则数组下标溢出，程序崩溃。
解决的方案：将middle=(left+right)/2改为middle=left+(right-left)/2即可。即利用减法代替加法，从而消除上溢。
参考自《代码之美》