亲宝软件园·资讯

展开

C/C++中使用二分查找算法 二分查找算法在C/C++程序中的应用示例

wuzhekai1985 人气:0
想了解二分查找算法在C/C++程序中的应用示例的相关内容吗,wuzhekai1985在本文为您仔细讲解C/C++中使用二分查找算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点: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; 
} 

       上面给出的二分查找是迭代法实现,当然也可以用递归的方式实现。代码如下:

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

       注意到数组的元素有正数,负数,零,最大值,最小值。通常会忘掉负数的测试,引入最大值和最小值,主要是为了边界测试。
       第一,测试了中值下标的计算。另外写了一个小函数,单独测试。考虑到内存可能放不下这么大的数组,因此只是模拟测试,并没有真正申请这么大的空间,但是对于中值下标的测试足够了。
       第二,冒烟测试。即做一些最基本的测试。测试通过后进行边界测试。
       第三,边界测试。这里有三种类型,一是针对数组元素个数,分别是0个,1个。二是针对元素位置,分别是首个元素,中间元素,末尾元素。三是针对元素值,有最大值,最小值,0等测试。
       第四,自动化测试。这里自动生成测试的数组,然后针对每个元素进行成功查找测试。
       第五,自动化测试,只不过数组的元素是随机值。
       第五,性能测试。这里相关代码没有列出。以上测试都通过时,可以修改查找算法,添加性能测试的代码。其实可以简单添加一个比较的计数器。返回值从原来的查找结果改为比较的计数器值即可。代码比较简单,就不列了。

Note:二分查找容易忽略的一个bug
对于二分查找算法,相信大家肯定不会陌生。算法从一个排好序的数组中找指定的元素,如果找到了返回该元素在数组中的索引,否则返回-1。下面给出了解法。

//a为排好序的数组,n为数组的大小,x为指定元素 
int binarySearch(int a[], int n, int x) 
{ 
 int left = 0, right = n-1, middle = 0; 
 int tmp = 0; 
 while(left <= right) 
 { 
   middle = (left + right)/2; 
   tmp = a[middle]; 
   if(x < tmp) right = middle - 1; 
   else if(x > tmp) left = middle + 1; 
   else return middle; 
 } 
 return -1; 
} 

      乍看没有错误,但是不幸的是,该程序存在一个bug。当数组极大时,(left+right)可能为负数,则数组下标溢出,程序崩溃。
解决的方案:将middle=(left+right)/2改为middle=left+(right-left)/2即可。即利用减法代替加法,从而消除上溢。
      参考自《代码之美》

加载全部内容

相关教程
猜你喜欢
用户评论