C++ 中 lower_bound 与 upper_bound 函数详解
一、核心定义与区别
1. lower_bound
- 作用：在有序序列中查找第一个不小于目标值的元素位置。
- 返回值：若目标值存在，返回第一个匹配元素的迭代器；若不存在，返回首个大于目标值的元素的迭代器。
- 示例：在序列
{1,2,4,4,5}中查找 4，返回第一个 4 的位置（索引 2）。 - 示例：用
lower_bound在{12,15,17,19,20,22,23,26,29,35,40,51}中查找 21 时返回 22 的索引位置。
2. upper_bound
- 作用：在有序序列中查找第一个大于目标值的元素位置。
- 返回值：若目标值存在，返回最后一个匹配元素的下一个位置；若不存在，行为与
lower_bound一致。 - 示例：在相同序列
{1,2,4,4,5}中查找 4，返回第一个 5 的位置（索引 4）。 - 示例：用
upper_bound在{12,15,17,19,20,22,23,26,29,35,40,51}中查找 21 时返回 22 的位置。
关键区别
| 特性 | lower_bound | upper_bound |
|---|---|---|
| 等价元素处理 | 指向第一个等价元素 | 指向最后一个等价元素的下一个位置 |
| 插入位置 | 插入后位于相同元素之前 | 插入后位于相同元素之后 |
| 目标值不存在时返回值 | 第一个大于目标值的元素位置 | 同上 |
二、使用条件与时间复杂度
1. 前提条件
- 序列必须已按升序排列（或按自定义比较规则有序）。若未排序，结果未定义。
2. 时间复杂度
- 均为 O(log n)，基于二分查找实现。
三、实际应用场景
插入元素保持有序性
在有序容器中插入新元素时，确定插入位置。
auto pos = upper_bound(v.begin(), v.end(), new_value);
v.insert(pos, new_value); // 插入后序列仍有序
自定义排序规则
支持传入比较函数，处理复杂数据结构或非默认排序：
