快捷導(dǎo)航

二分查找算法在C/C++程序中的應(yīng)用示例

更新時(shí)間：2016年03月15日 14:16:04 作者：wuzhekai1985

這篇文章主要介紹了二分查找算法在C/C++程序中的使用示例,文中最后提到了使用二分查找法一個(gè)需要注意的地方,需要的朋友可以參考下

二分查找算法的思想很簡(jiǎn)單，《編程珠璣》中的描述：在一個(gè)包含t的數(shù)組內(nèi)，二分查找通過(guò)對(duì)范圍的跟綜來(lái)解決問(wèn)題。開(kāi)始時(shí)，范圍就是整個(gè)數(shù)組。通過(guò)將范圍中間的元素與t比較并丟棄一半范圍，范圍就被縮小。這個(gè)過(guò)程一直持續(xù)，直到在t被發(fā)現(xiàn)，或者那個(gè)能夠包含t的范圍已成為空。
Donald Knuth在他的《Sorting and Searching》一書(shū)中指出，盡管第一個(gè)二分查找算法早在1946年就被發(fā)表，但第一個(gè)沒(méi)有bug的二分查找算法卻是在12年后才被發(fā)表出來(lái)。其中常見(jiàn)的一個(gè)bug是對(duì)中間值下標(biāo)的計(jì)算，如果寫(xiě)成(low+high)/2，當(dāng)low+high很大時(shí)可能會(huì)溢出，從而導(dǎo)致數(shù)組訪問(wèn)出錯(cuò)。改進(jìn)的方法是將計(jì)算方式寫(xiě)成如下形式：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; 
}

這里注意一點(diǎn)，由于使用的是不對(duì)稱(chēng)區(qū)間，所以下標(biāo)的調(diào)整看上去有點(diǎn)不規(guī)整。一個(gè)是u=m，另一個(gè)是l=m+1。其實(shí)很好理解，調(diào)整前區(qū)間的形式應(yīng)該是 [ )的形式，如果中間值比查找值小，那么調(diào)整的是左邊界，也就是閉的部分，所以加1；否則，調(diào)整是右邊界，是開(kāi)的部分，所以不用減1。調(diào)整后仍是[ )的形式。當(dāng)然也可以寫(xiě)成對(duì)稱(chēng)的形式。代碼如下：

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

這樣也看上去比較規(guī)整，但是有個(gè)不足。如果想把程序改成“純指針”的形式，就會(huì)有麻煩。修改成純指針的代碼如下：

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

當(dāng)n為0時(shí)，會(huì)引用無(wú)效地址。而用非對(duì)稱(chēng)區(qū)間則不會(huì)有這個(gè)問(wèn)題。代碼如下：

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

上面給出的二分查找是迭代法實(shí)現(xiàn)，當(dāng)然也可以用遞歸的方式實(shí)現(xiàn)。代碼如下：

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;

上述這些二分算法，若數(shù)組元素重復(fù)，返回的是重復(fù)元素的某一個(gè)元素。如果希望返回被查找元素第一次出現(xiàn)的位置，則需要修改代碼。下面給出了一種解法：

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

至此二分算法的代碼討論結(jié)束，下面討論一下程序的測(cè)試問(wèn)題?！洞a之美》有一章專(zhuān)門(mén)介紹二分查找算法的測(cè)試，非常漂亮。這里班門(mén)弄斧，簡(jiǎn)單給出幾個(gè)測(cè)試用例。針對(duì)binarysearch1。測(cè)試程序如下：

#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}; 
 //中值下標(biāo)計(jì)算的測(cè)試 
 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); 
 
 //冒煙測(cè)試 
 assert(bs1(a,9,0)==5); 
 assert(bs1(a,9,1)==6); 
 assert(bs1(a,9,2)==-1); 
 
 //邊界測(cè)試 
 assert(bs1(a,0,1)==-1);       //0個(gè)元素 
 assert(bs1(a,1,-2147483648)==0);  //1個(gè)元素 成功 
 assert(bs1(a,1,-2147483647)==-1);  //1個(gè)元素 失敗 
 
 assert(bs1(a,9,-2147483648)==0);  //首個(gè)元素 
 assert(bs1(a,9,-3)==4);       //中間元素 
 assert(bs1(a,9,2147483647)==8);  //末尾元素 
 
 //自動(dòng)化測(cè)試 
 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); 
  } 
 } 
 
 //自動(dòng)化測(cè)試 引入隨機(jī)數(shù) 
 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; 
}

       注意到數(shù)組的元素有正數(shù)，負(fù)數(shù)，零，最大值，最小值。通常會(huì)忘掉負(fù)數(shù)的測(cè)試，引入最大值和最小值，主要是為了邊界測(cè)試。
       第一，測(cè)試了中值下標(biāo)的計(jì)算。另外寫(xiě)了一個(gè)小函數(shù)，單獨(dú)測(cè)試?？紤]到內(nèi)存可能放不下這么大的數(shù)組，因此只是模擬測(cè)試，并沒(méi)有真正申請(qǐng)這么大的空間，但是對(duì)于中值下標(biāo)的測(cè)試足夠了。
       第二，冒煙測(cè)試。即做一些最基本的測(cè)試。測(cè)試通過(guò)后進(jìn)行邊界測(cè)試。
       第三，邊界測(cè)試。這里有三種類(lèi)型，一是針對(duì)數(shù)組元素個(gè)數(shù)，分別是0個(gè)，1個(gè)。二是針對(duì)元素位置，分別是首個(gè)元素，中間元素，末尾元素。三是針對(duì)元素值，有最大值，最小值，0等測(cè)試。
       第四，自動(dòng)化測(cè)試。這里自動(dòng)生成測(cè)試的數(shù)組，然后針對(duì)每個(gè)元素進(jìn)行成功查找測(cè)試。
       第五，自動(dòng)化測(cè)試，只不過(guò)數(shù)組的元素是隨機(jī)值。
       第五，性能測(cè)試。這里相關(guān)代碼沒(méi)有列出。以上測(cè)試都通過(guò)時(shí)，可以修改查找算法，添加性能測(cè)試的代碼。其實(shí)可以簡(jiǎn)單添加一個(gè)比較的計(jì)數(shù)器。返回值從原來(lái)的查找結(jié)果改為比較的計(jì)數(shù)器值即可。代碼比較簡(jiǎn)單，就不列了。

Note：二分查找容易忽略的一個(gè)bug
對(duì)于二分查找算法，相信大家肯定不會(huì)陌生。算法從一個(gè)排好序的數(shù)組中找指定的元素，如果找到了返回該元素在數(shù)組中的索引，否則返回-1。下面給出了解法。

//a為排好序的數(shù)組，n為數(shù)組的大小，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; 
}

乍看沒(méi)有錯(cuò)誤，但是不幸的是，該程序存在一個(gè)bug。當(dāng)數(shù)組極大時(shí)，(left+right)可能為負(fù)數(shù)，則數(shù)組下標(biāo)溢出，程序崩潰。
解決的方案：將middle=(left+right)/2改為middle=left+(right-left)/2即可。即利用減法代替加法，從而消除上溢。
參考自《代碼之美》

您可能感興趣的文章: