標(biāo)準(zhǔn)的二分查找，大家可能都已經(jīng)能記在腦海里了，但是稍微變形一下，可能就會出問題。

本文寫了一個(gè)二分查找算法，并且做了一個(gè)測試的腳手架，用二分查找和普通算法的結(jié)果進(jìn)行比較來驗(yàn)證算法的正確性。

1 #include<iostream> 2 #include<string> 3 using namespace std; 4 int find(int a[],int n ,int x) 5 { 6 int i=0,j=n-1; 7 int ret=-1; 8 while(i<j) 9 { 10 int mid=i+(j-i)/2; 11 if(a[mid]==x) 12 { 13 int k=mid; 14 while(k>=0&&a[k]==a[mid]) 15 k--; 16 ret=k+1; 17 return ret; 18 } 19 else if(a[mid]>x) 20 { 21 j=mid; 22 } 23 else 24 { 25 i=mid+1; 26 } 27 } 28 if(i==j&&a[i]>=x) 29 ret=i; 30 return ret; 31 } 32 int find2(int a[],int n,int x) 33 { 34 for(int i=0;i<n;i++) 35 { 36 if(a[i]>=x) 37 { 38 return i; 39 } 40 } 41 return -1; 42 } 43 #define N 100 44 int a[N],x; 45 46 int comp(const void *p1,const void *p2) 47 { 48 return *((int*)p2)<*((int*)p1)?1:-1; 49 } 50 int main() 51 { 52 int j; 53 for(j=0;j<1000000;j++) 54 { 55 cout<<"-----NO:"<<(j+1)<<endl; 56 int i; 57 for(i=0;i<N;i++) 58 { 59 a[i]=rand()%30; 60 } 61 qsort(a,sizeof(a),sizeof(int),comp); 62 x=rand()%30; 63 64 int ret=find(a,N,x); 65 int ret2=find2(a,N,x); 66 if(ret!=ret2) 67 { 68 69 cout<<"error---------------------"<<endl; 70 for(i=0;i<N;i++) 71 { 72 cout<<" "<<a[i]; 73 } 74 cout<<endl; 75 cout<<"x="<<x<<endl; 76 cout<<"find:"<<ret<<" ;find2:"<<ret2<<endl; 77 return 0; 78 } 79 return 0; 80 』

在上面代碼中，隨即生成測試用例，進(jìn)行了一百萬比較來驗(yàn)證程序的正確性。

轉(zhuǎn)載于:https://www.cnblogs.com/dyc0113/p/4593114.html

總結(jié)

以上是生活随笔為你收集整理的二分查找：在有序数组中搜索大于等于x的数的最小下标的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。