二分查找算法在C/C++法式中的運用示例。本站提示廣大學習愛好者：（二分查找算法在C/C++法式中的運用示例）文章只能為提供參考，不一定能成為您想要的結果。以下是二分查找算法在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便可。即應用減法取代加法，從而清除上溢。
參考自《代碼之美》
