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如下图所示：如果所有元素都小于val，则返回last的位置且last的位置是越界的！！~
2.插入：举例如下：
一个数组num序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,20,111。pos为要插入的位置的下标，则
pos=lower_bound(num,num+8,3)-num,pos=0。即num数组的下标为0的位置。
pos=lower_bound(num,num+8,9)-num,pos=1。即num数组的下标为1的位置（即10所在的位置）。
pos=lower_bound(num,num+8,111)-num,pos=8。即num数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。
pos=upper_bound(num,num+8,20)-num,pos=3。即num数组中的下标为3的位置。
1.lower_bound函数源代码：
view source print ? 01. //这个算法中，first是最终要返回的位置 02. int lower_bound(int *array, int size, int key) 03. { 04. int first = 0, middle; 05. int half, len; 06. len = size; 07. 08. while(len > 0) { 09. half = len >> 1; 10. middle = first + half; 11. if(array[middle] < key) { 12. first = middle + 1; 13. len = len-half-1; //在右边子序列中查找 14. } 15. else 16. len = half; //在左边子序列（包含middle）中查找 17. } 18. return first; 19. }
2.upper_bound函数源代码：
view source print ? 01. int upper_bound(int *array, int size, int key) 02. { 03. int len = size-1; 04. int half, middle; 05. 06. while(len > 0){ 07. half = len >> 1; 08. middle = first + half; 09. 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. }
转载于:https://www.cnblogs.com/flyljz/p/10991942.html
