C++中的 lower_bound 和 upper_bound：一篇讲清楚
在刷题或者写代码的时候，lower_bound和upper_bound是两个非常高频但又容易用错的函数。很多人知道“能用”，但不知道“为什么这样用”。
这篇文章不搞花里胡哨的定义，直接从实际理解、使用方式、常见坑这几个角度讲清楚。
这两个函数到底是干嘛的；一句话版本
在一个有序序列中：
lower_bound：找到第一个 >= x 的位置
upper_bound：找到第一个 > x 的位置
记住这句话基本就够用了。
举个最简单的例子
vector<int> v = {1, 2, 2, 2, 3, 4};查找2：
lower_bound(v.begin(), v.end(), 2) → 指向第一个 2 upper_bound(v.begin(), v.end(), 2) → 指向第一个 3也就是说：
lower_bound → 左边界 upper_bound → 右边界返回的是什么；别搞错了
这两个函数返回的不是下标，而是：
迭代器（iterator）
如果你要下标，需要这样写：
int pos = lower_bound(v.begin(), v.end(), x) - v.begin();最常见用途一；判断元素是否存在
auto it = lower_bound(v.begin(), v.end(), x); if (it != v.end() && *it == x) { cout << "存在"; }解释：
lower_bound 找到第一个 >= x 的位置
如果这个位置刚好等于 x → 说明存在
最常见用途二；统计某个数出现次数
int cnt = upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);这行代码非常经典，直接记住：
出现次数 = 右边界 - 左边界
最常见用途三；插入位置
如果你要往有序数组中插入一个元素：
auto it = lower_bound(v.begin(), v.end(), x); v.insert(it, x);这样插入之后，数组依然有序。
必须注意的前提；一定要有序
这两个函数的前提是：
序列必须是有序的（默认升序）
如果是乱序数组：
结果是错的
但不会报错（这是最坑的地方）
自定义排序怎么办
如果你用的是自定义排序，比如降序：
sort(v.begin(), v.end(), greater<int>());那你就必须传入同样的比较函数：
lower_bound(v.begin(), v.end(), x, greater<int>());否则结果是错误的。
手写理解；它本质就是二分
可以用一个简单的“手写版本”来理解 lower_bound：
int l = 0, r = n; while (l < r) { int mid = (l + r) / 2; if (v[mid] >= x) r = mid; else l = mid + 1; }最终：
l 就是 lower_bound 的位置而 upper_bound 只是把条件改成：
v[mid] > x常见坑总结
; 忘了数组必须有序
很多人直接用在乱序数组上，结果完全不对
; 把返回值当下标
记住它返回的是迭代器
; 边界没判断
it != v.end()一定要写
; 自定义排序没传比较函数
这是中高级选手最容易翻车的地方
一句话记忆法
如果你懒得记一堆东西，就记这一句：
lower_bound 找“第一个不小于”，upper_bound 找“第一个大于”
最后
这两个函数本质上就是“封装好的二分查找”，但它们的威力在于：
写法简洁
不容易出错
能直接解决很多区间问题
建议你多用几次，比如：
统计区间
去重处理
LIS（最长上升子序列）
用多了，自然就顺手了。