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实现的
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(int argc, char** argv) { int arr[] = {3,2,5,4,8,0,9,5,6}; sort(arr,arr+9); cout << lower_bound(arr,arr+9,5)-arr << endl; cout << upper_bound(arr,arr+9,5)-arr << endl; vector<int> vec; vec.push_back(3); vec.push_back(2); vec.push_back(5); vec.push_back(4); vec.push_back(8); vec.push_back(0); vec.push_back(9); vec.push_back(5); vec.push_back(6); sort(vec.begin(), vec.end()); cout << lower_bound(vec.begin(),vec.end(),5)-vec.begin() << endl; cout << upper_bound(vec.begin(),vec.end(),5)-vec.begin() << endl; return 0; }
输出：
4 6 4 6
原文：http://www.cnblogs.com/scarecrow-blog/p/4568948.html