二分查找

      二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

 

STL自带了两个二分查找函数：

     ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

     ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

     lower_bound和upper_bound如下图所示：

 

 下面是lower_bound的源码：

1 int lower_bound(int *array, int size, int key) 2 { 3     int first = 0, middle; 4     int half, len; 5     len = size; 6  7     while(len > 0) { 8         half = len >> 1; 9         middle = first + half;10         if(array[middle] < key) {     11             first = middle + 1;          12             len = len-half-1;       //在右边子序列中查找13         }14         else15             len = half;            //在左边子序列（包含middle）中查找16     }17     return first;18 }

以及upper_bound的源码：

1 int upper_bound(int *array, int size, int key) 2 { 3     int first = 0, len = size; 4     int half, middle; 5  6     while(len > 0){ 7         half = len >> 1; 8         middle = first + half; 9         if(array[middle] > key)     //中位数大于key,在包含last的左半边序列中查找。10             len = half;11         else{12             first = middle + 1;    //中位数小于等于key,在右半边序列中查找。13             len = len - half - 1;14         }15     }16     return first;17 }