C / C++ / 系统课时
lower_bound 能解决什么问题
lower_bound 能解决什么问题
在有序数据里,很多需求并不是简单判断“有没有”,而是寻找一个精确边界:第一个不小于目标的位置、重复值的起点与终点,或者新元素应该插入在哪里。lower_bound 和 upper_bound 就是为这些场景准备的二分区间算法。
学习目标
- 理解
lower_bound与upper_bound返回位置的含义 - 用两个边界定位重复元素形成的半开区间
- 使用
lower_bound找到保持序列有序的插入位置
lower_bound 找到的是边界
对于默认的升序比较,std::lower_bound(first, last, value) 返回第一个不小于 value 的元素。如果所有元素都小于目标,它会返回 last。
std::upper_bound 则返回第一个大于 value 的元素。因此,当目标存在重复值时,两者正好围出目标值所在的半开区间 [lower, upper)。
例如序列 1 2 2 2 4 7 查找 2:lower_bound 指向下标 1 的第一个 2,upper_bound 指向下标 4 的 4,所以三个 2 位于区间 [1, 4)。

这个定义非常适合边界问题,因为目标不存在时仍然会返回一个有意义的位置,而不是只能告诉你“失败”。
定位重复值和插入点
下面同时演示重复值区间和有序插入。原始序列已经升序,因此可以直接使用默认比较规则。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums{1, 2, 2, 2, 4, 7};
// 两个边界围出所有值为 2 的元素。
auto first = std::lower_bound(nums.begin(), nums.end(), 2);
auto last = std::upper_bound(nums.begin(), nums.end(), 2);
std::cout << "lower index: " << first - nums.begin() << '\n';
std::cout << "upper index: " << last - nums.begin() << '\n';
std::cout << "count: " << last - first << '\n';
// 3 不存在,但 lower_bound 会给出保持升序的插入位置。
auto insert_pos = std::lower_bound(nums.begin(), nums.end(), 3);
std::cout << "insert index: " << insert_pos - nums.begin() << '\n';
nums.insert(insert_pos, 3);
for (int value : nums) {
std::cout << value << ' ';
}
std::cout << '\n';
}预期输出:
lower index: 1
upper index: 4
count: 3
insert index: 4
1 2 2 2 3 4 7插入 3 时,返回的位置指向原来的 4。在该位置执行 insert 后,前面的元素都小于 3,后面的元素都不小于 3,因此序列仍保持升序。
三种常见需求怎样选择
只判断目标是否存在时,binary_search 的布尔结果最直接。需要第一个可放置位置时使用 lower_bound;需要确定重复值结束位置时使用 upper_bound。如果同时需要重复值的左右边界,还可以使用 std::equal_range 一次得到等价的两个迭代器。
查找某个值 x 是否存在时,也可以先调用 lower_bound,再检查返回迭代器没有到达 end(),并且其元素确实等于 x。这种写法的优势是同一个结果还能继续用于获取位置或执行插入。
有序和比较器仍然是前提
这些边界算法与 binary_search 一样依赖有序区间。默认升序时,“第一个不小于目标”很好理解;使用自定义比较器后,更通用的定义是:lower_bound 返回第一个不再被比较器判定为“位于目标之前”的位置。
例如数据按降序排列时,应在排序和边界查找中都使用 std::greater<int>。不要对降序数据直接套用默认版本,否则返回位置没有可靠意义。
对于 std::vector、std::deque 这类支持随机访问的有序范围,lower_bound 和 upper_bound 都只需要 次比较。它们把“找某个元素”扩展成了“找有序区间的边界”,因此尤其适合区间统计、重复值处理和保持顺序的插入定位。