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如下图所示:
调用时注意,传入的firest 是第一元素的索引,传入的last是最后一个元素下一个元素的索引。
返回时,若所有元素都比targe 小,则返回last
STL 的equal_range是基于lower_bound 和upper_bound实现的
1, lower_bound
这个序列中可能会有很多重复的元素,也可能所有的元素都相同,为了充分考虑这种边界条件,STL中的lower_bound算法总体上是才用了二分查找的方法,但是由于是查找序列中的第一个出现的值大于等于val的位置,所以算法要在二分查找的基础上做一些细微的改动。
1 int lower_bound(int* array, int low, int high, int key ) 2 { 3 4 5 int mid = 0; 6 while(low < high) 7 { 8 mid = (low + high)/2; 9 if(array[mid] >= key)10 //若中位数的值大于等于key,我们要在左边子序列查找,但有可能middle处就是最终位置,所以我们要包含mid,让high保持不动, 让low不断逼近high。11 high = mid;// 注意,包含mid,high=mid,不是high = mid+1;12 else13 low = mid+1; //若中位数的值小于key的值,我们要在右边子序列中查找, 不包含mid14 15 } 16 return high;17 18 }
2, upper_bound
upper_bound返回的是最后一个大于等于val的位置,也是有一个新元素val进来时的插入位置
1 int upper_bound(int* array, int low, int high, int key ) 2 { 3 4 5 int mid = 0; 6 while(low < high) 7 { 8 mid = (low + high)/2; 9 if(array[mid] > key)10 //若中位数的值大于等于key,我们要在左边子序列查找,但有可能middle处就是最终位置,所以我们要包含mid,让high保持不动, 让low不断逼近high。11 high = mid;// 注意,包含mid,high=mid,不是high = mid+1;12 else13 low = mid+1; //若中位数的值小于key的值,我们要在右边子序列中查找, 不包含mid14 15 } 16 return high;17 18 }
另外,也可以用一个变量来记录当前的位置,写起来也很简单。。在传统二分基础上加两个判断
1 #if 1 2 int my_lower_bound(int *array, int low, int high, int key) 3 { 4 int mid, pos= high; 5 high --; 6 7 while(low <= high) 8 { 9 mid = (low + high)/2;10 if(array[mid] >= key){ 11 if(mid < pos)12 pos = mid;13 high = mid- 1; 14 }15 else{16 low = mid + 1; 17 }18 }19 return pos;20 }21 int my_upper_bound(int *array, int low, int high, int key)22 {23 int mid, pos= high; 24 high --;25 26 while(low <= high)27 {28 mid = (low + high)/2;29 if(array[mid] > key){ 30 if(mid < pos)31 pos = mid;32 high = mid- 1; 33 }34 else{35 low = mid + 1; 36 }37 }38 return pos;39 }40 #endif