二分查找算法的思想很簡單，《編程珠璣》中的描述： 在一個包含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; }
至此二分算法的代碼討論結束，下面討論一下程序的測試問題?！洞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); } } //自動化測試 引入隨機數 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即可。即利用減法代替加法，從而消除上溢。
參考自《代碼之美》
新聞熱點
疑難解答
圖片精選
