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

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

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

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

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ī)整，但是有個不足。如果想把程序改成“純指針”的形式，就會有麻煩。修改成純指針的代碼如下：

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時，會引用無效地址。而用非對稱區(qū)間則不會有這個問題。代碼如下：

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

上面給出的二分查找是迭代法實現(xiàn)，當然也可以用遞歸的方式實現(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ù)組元素重復，返回的是重復元素的某一個元素。如果希望返回被查找元素第一次出現(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; 
}

至此二分算法的代碼討論結束，下面討論一下程序的測試問題?！洞a之美》有一章專門介紹二分查找算法的測試，非常漂亮。這里班門弄斧，簡單給出幾個測試用例。針對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); 
  } 
 } 
 
 //自動化測試 引入隨機數(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ù)，負數(shù)，零，最大值，最小值。通常會忘掉負數(shù)的測試，引入最大值和最小值，主要是為了邊界測試。
       第一，測試了中值下標的計算。另外寫了一個小函數(shù)，單獨測試?？紤]到內(nèi)存可能放不下這么大的數(shù)組，因此只是模擬測試，并沒有真正申請這么大的空間，但是對于中值下標的測試足夠了。
       第二，冒煙測試。即做一些最基本的測試。測試通過后進行邊界測試。
       第三，邊界測試。這里有三種類型，一是針對數(shù)組元素個數(shù)，分別是0個，1個。二是針對元素位置，分別是首個元素，中間元素，末尾元素。三是針對元素值，有最大值，最小值，0等測試。
       第四，自動化測試。這里自動生成測試的數(shù)組，然后針對每個元素進行成功查找測試。
       第五，自動化測試，只不過數(shù)組的元素是隨機值。
       第五，性能測試。這里相關代碼沒有列出。以上測試都通過時，可以修改查找算法，添加性能測試的代碼。其實可以簡單添加一個比較的計數(shù)器。返回值從原來的查找結果改為比較的計數(shù)器值即可。代碼比較簡單，就不列了。

Note：二分查找容易忽略的一個bug
對于二分查找算法，相信大家肯定不會陌生。算法從一個排好序的數(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; 
}

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

上一篇：解析C++函數(shù)的默認參數(shù)和占位參數(shù)及較之C語言的拓展

欄目：C語言

下一篇：C語言將數(shù)組中元素的數(shù)排序輸出的相關問題解決

本文標題：二分查找算法在C/C++程序中的應用示例

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/2425.html

更多C語言

雷火电竞-中国电竞赛事及体育赛事平台

C語言

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

您可能感興趣的文章

閱讀排行

本欄相關

隨機閱讀