二分里面好用的函数

upper_bound(ForwardIterator first, ForwardIterator last,const T& val))

ForwardIterator first是一个

ForwardIterator first 是指要查询的数列的起点

ForwardIterator last 是值要查询的数列的终点

const T&val 表明输入进去的值

官方的原文

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

返回一个迭代器,指向第一个元素超过val的地址

因为返回的是地址,所以我们求下标的时候就要把这个地址减去数列的起始地址

lower_bound(ForwardIterator first, ForwardIterator last,const T& val))

他们的参数都是一样的，不一样的在功能上

官方的原文

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val

返回一个迭代器,指向第一个不小于val的值的地址,也要减去数列的起始地址才是下标

下面是官方的解释代码

// lower_bound/upper_bound example #include <iostream> // std::cout #include <algorithm> // std::lower_bound, std::upper_bound, std::sort #include <vector> // std::vector int main () { 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; }

官方解释文档如下

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

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