lower_bound / upper_bound

找小于等于的最后一个位置

lower_bound 找 >= x 第一个位置
upper_bound 找 > x 的第一个位置
那么如何找 < x 的最后一个位置呢？直接 lower_bound 再减一
那么如何找 <= x 的最后一个位置呢？直接 upper_bound 再减一

计算出现次数

可以通过 upper_bound - lower_bound 计算出现次数

易错点

lower_bound / upper_bound 的返回值有n+1种可能，其中n是数组长度
比如 lower_bound(a, a + n, x) - a; 的结果最小可能是0，最大可能是n，但是并不存在a[n]这个元素

判断x在数组中是否出现过，不能用 *lower_bound(a, a + n, x) == x
因为 lower_bound 返回的位置可能是无效的位置

注意区分函数和成员函数

STL中有函数 lower_bound / upper_bound
参数是
lower_bound(数组开始, 数组结束, 查询的值)

对于 set 和 map 来说，还有一种写法

int b[100];
lower_bound(b, b + n, x); // 返回指针

vector<int> a;
lower_bound(a.begin(), a.end(), x); // 返回 vector<int>::iterator

set<int> s;
s.lower_bound(x); // 返回 set<int>::iterator