C++ 中 lower_bound 与 upper_bound 核心用法
核心定义与区别
在有序序列里找位置，这两个函数是标配。理解它们的返回值逻辑，能避免很多低级错误。
lower_bound
作用：找到第一个不小于目标值的元素。
返回值：如果找到了，返回该元素的迭代器；没找到，返回第一个比它大的元素位置。
比如 {1,2,4,4,5} 找 4，返回索引 2（第一个 4）。
upper_bound 作用：找到第一个大于目标值的元素。 返回值：如果找到了，返回最后一个匹配元素的下一个位置；没找到，行为同 lower_bound。 同样序列找 4，返回索引 4（数字 5 的位置）。
| 特性 | lower_bound | upper_bound |
|---|---|---|
| 等价元素处理 | 指向第一个等价元素 | 指向最后一个等价元素的下一个位置 |
| 插入位置 | 插入后位于相同元素之前 | 插入后位于相同元素之后 |
| 目标值不存在时返回值 | 第一个大于目标值的元素位置 | 同上 |
使用条件与时间复杂度
前提很简单：序列必须已排序。升序或按自定义规则有序都行，要是乱序调用，结果未定义，别问为什么问了就是 UB。
时间复杂度都是 O(log n)，底层基于二分查找，效率很高。
实际应用场景
保持有序插入 往容器里塞新数据，想维持顺序，直接算出位置插进去就行。
auto pos = upper_bound(v.begin(), v.end(), new_value);
v.insert(pos, new_value); // 插入后序列仍有序
自定义排序规则
默认是按 < 比较，复杂点的数据结构可以传比较函数。
// 按个位数排序的数组
bool cmp(int a, int b) {
return a % 10 < b % 10;
}
auto it = lower_bound(arr, arr + n, 36, cmp); // 查找个位数 >=6 的第一个元素
统计出现次数 利用两个函数的差值，区间跨度就是数量。
int count = upper_bound(v.begin(), v.end(), target) - lower_bound(v.begin(), v.end(), target);
检查元素是否存在 结合 lower_bound 的结果和目标值比对。
auto it = lower_bound(v.begin(), v.end(), target);
bool exists = (it != v.end()) && (*it == target);
注意事项与常见误区
-
必须保证序列有序 这是最容易翻车的地方。对乱序数组调用可能返回错误位置，甚至导致程序崩溃。
-
迭代器越界检查 拿到返回值别急着解引用，先判断是不是
end()。 -
自定义比较函数的一致性 比较逻辑得跟序列排序规则一致。比如降序序列得用
greater，不能用默认的less。 -
等价元素的处理差异 如果需要获取所有相等元素的范围，直接用
equal_range更省事，它内部就是调用了这两个函数。
代码示例
下面这段代码演示了基本用法，注意看注释里的输出逻辑。
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> v = {1, 2, 4, 4, 5, 7, 8};
int target = 4;
// lower_bound 示例
auto low = lower_bound(v.begin(), v.end(), target);
cout << "lower_bound 位置：" << (low - v.begin()) << "，值：" << *low << endl;
// 输出 2, 4
// upper_bound 示例
auto up = upper_bound(v.begin(), v.end(), target);
cout << "upper_bound 位置：" << (up - v.begin()) << "，值：" << *up << endl;
// 输出 4, 5
return 0;
}
总结
lower_bound 和 upper_bound 是处理有序序列的利器。只要记住'小于等于'和'大于'的区别，配合二分查找的高效性，能解决大部分查找、统计和插入问题。使用时务必确认数据已排序，并注意边界情况。
