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