上面给出的二分查找是迭代法实现，当然也可以用递归的方式实现。代码如下：
int binarysearch3(int a[],int l,int u,int x)
int m=l+((u-l)>>1);
if(l<=u)
{
if(x<a[m])
return binarysearch3(a,l,m-1,x);
else if(x==a[m])
return m;
else
return binarysearch3(a,m+1,u,x);
}
return -1;
上述这些二分算法，若数组元素重复，返回的是重复元素的某一个元素。如果希望返回被查找元素第一次出现的位置，则需要修改代码。下面给出了一种解法：
int binarysearch4(int a[],int n,int x)
{
int l,u,m;
int flag=-1;
l=0;u=n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m;
else if(x==a[m])
flag=u=m;
else
l=m+1;
}
return flag;
}
下面是《编程珠玑》上的解法：
int binarysearch4(int a[],int n,int x)
{
int l,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>
using namespace std;
int calmid(int l,int u) { return l+((u-l)>>1); }
int binarysearch1(int a[],int n,int x);
#define bs1 binarysearch1
int main()
{
long start,end;
start=clock();
int a[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); //末尾元素
//自动化测试
int b[10000];
int i,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++)
{
int x=rand();
int k=bs1(b,i+1,x);
if(k!=-1)
assert(b[k]==x);
}
}
end=clock();
cout<<(end-start)/1000.0<<'s'<<endl;
return 0;
}
