二分查找算法

二分查找

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

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         else
15             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 }