C++ STL lower_bound 和 upper_boun

1. 说明

lower_bound 返回范围[first,last)内第一个大于等于指定值val的元素的迭代器。

upper_bound 返回范围[first,last)内第一个大于指定值val的元素的迭代器。

两个函数联合起来使用，就可以找出指定值val在范围[first,last)的上下索引。

注意：

1. 使用这两个函数的前提是范围[first,last)内的元素是有序的。
2. 如果val小于[first, last)所有值，返回first迭代器
3. 如果val大于[first, last)所有值，返回last迭代器

函数签名如下：

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, 
                             ForwardIterator last,
                             const T& val);

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, 
                             ForwardIterator last,
                             const T& val);

2. 头文件

#include <algorithm>

3. 例子

#include <iostream>
#include <vector>
#include <algorithm>


int main(int argc, char **argv) 
{  
    int myints[] = {10,20,30,30,20,10,10,20};
    std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

    std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

    std::vector<int>::iterator low,up;
    low=std::lower_bound (v.begin(), v.end(), 20); //          ^
    up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

    std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
    std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
  
    return 0;
}

结果：

lower_bound at position 3
upper_bound at position 6

数组中有多个20,第一个大于等于20的元素是第3个元素（索引是从0开始的）。
数组中第一个大于20的元素是第6个元素。

4. 参考

http://www.cplusplus.com/reference/algorithm/lower_bound/
http://www.cplusplus.com/reference/algorithm/upper_bound/