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