## STL經典算法集錦<五>之查找（lower_bound/upper_bound/binary_search） 這三個算法都比較的常用，而且具有一定的相似的性。理論依據也很明顯，下面就直接貼出自己的實現版本。其中lower_bound與upper_bound實現了兩個版本。版本一與STL的實現方法完全相同，以數據的總長度折半，版本二則是直接取前后的中點。當然本質上沒有太大區別。 **lower_bound版本一：** ~~~ int lowerBound(int array[],int left,int right,int value) { int mid=0,half=0; int len=(right+left+1)/2; while(len>0) { half=len>>1; //數據長度折半 mid=left+half; //計算中點 if (array[mid]<value) //調整總長與起點 { len=len-half-1; left=mid+1; } else len=half; } return left; } ~~~ **lower_bound版本二：** ~~~ int lowerBound(int array[],int left,int right,int value) { int mid=0; while(left<right) { mid=(right+left)/2; //計算中點 if (array[mid]<value) //調整起點或者終點 left=mid+1; else right=mid; } return right; } ~~~ **upper_bound版本一：** ~~~ int upperBound(int array[],int left,int right,int value) { int mid=0,half=0; int len=(right+left+1)/2; while(len>0) { half=len>>1; //長度折半 mid=left+half; //計算中點 if (array[mid]>value) //調整長度與起點 len=half; else { len=len-half-1; left=mid+1; } } return left; } ~~~ **upper_bound版本二： ** ~~~ int upperBound(int array[],int left,int right,int value) { int mid=0; while(left<right) { mid=(right+left)/2; //計算中點 if (array[mid]>value) //調整起點或者終點 right=mid; else left=mid+1; } return right; } ~~~ **折半查找：** ~~~ int binarySearch(int array[],int left,int right,int value) { int mid; while(left<=right) { mid=(left&right)+((left^right)>>1); //防止溢出 if(array[mid]==value) return mid; else if (array[mid]<value) left=mid+1; else right=mid-1; } return -1; } ~~~ **可用測試代碼：** ~~~ int main() { srand(time(0)); int len=21; int array[len]; for(int i=0;i<len;i++) array[i]=rand()%200; sort(array,array+len); for(int i=0;i<len;i++) cout<<array[i]<<"\t"; cout<<endl; cout<<"\nresult:"<<binarySearch(array,0,len-1,33)<<endl; return 0; } ~~~