易采站长站为您分析二分查找算法在C/C++程序中的使用示例,文中最后提到了使用二分查找法一个需要注意的地方,需要的朋友可以参考下
二分查找算法的思想很简单，《编程珠玑》中的描述： 在一个包含t的数组内，二分查找通过对范围的跟综来解决问题。开始时，范围就是整个数组。通过将范围中间的元素与t比较并丢弃一半范围，范围就被缩小。这个过程一直持续，直到在t被发现，或者那个能够包含t的范围已成为空。
Donald Knuth在他的《Sorting and Searching》一书中指出，尽管第一个二分查找算法早在1946年就被发表，但第一个没有bug的二分查找算法却是在12年后才被发表出来。其中常见的一个bug是对中间值下标的计算，如果写成(low+high)/2，当low+high很大时可能会溢出，从而导致数组访问出错。改进的方法是将计算方式写成如下形式：low+ ( (high-low) >>1)即可。下面给出修改后的算法代码：
int binarysearch1(int a[],int n,int x)
{
int l,u,m;
l=0;u=n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m;
else if(x==a[m])
return m;
else
l=m+1;
}
return -1;
}
这里注意一点，由于使用的是不对称区间，所以下标的调整看上去有点不规整。一个是u=m，另一个是l=m+1。其实很好理解，调整前区间的形式应该是 [ )的形式，如果中间值比查找值小，那么调整的是左边界，也就是闭的部分，所以加1；否则，调整是右边界，是开的部分，所以不用减1。调整后仍是[ )的形式。当然也可以写成对称的形式。代码如下：
int binarysearch1(int a[],int n,int x)
{
int l,u,m;
l=0;u=n-1;
while(l<=u)
{
m=l+((u-l)>>1);
if(x<a[m])
u=m-1;
else if(x==a[m])
return m;
else
l=m+1;
}
return -1;
}
这样也看上去比较规整，但是有个不足。如果想把程序改成“纯指针”的形式，就会有麻烦。修改成纯指针的代码如下：
int binarysearch2(int *a,int n,int x)
{
int *l,*u,*m;
l=a;u=a+n-1;
while(l<=u)
{
m=l+((u-l)>>1);
if(x<*m)
u=m-1;
else if(x==*m)
return m-a;
else
l=m+1;
}
return -1;
}
当n为0时，会引用无效地址。而用非对称区间则不会有这个问题。代码如下：
int binarysearch2(int *a,int n,int x)
{
int *l,*u,*m;
l=a;u=a+n;
while(l<u)
{
m=l+((u-l)>>1);
if(x<*m)
u=m;
else if(x==*m)
return m-a;
else
l=m+1;
}
return -1;
}
