C++ lower_bound 与 upper_bound 核心用法解析
lower_bound 和 upper_bound 是 C++ 标准库 <algorithm> 头文件中的二分查找利器，专门用于在有序区间内高效定位元素。理解它们的区别和适用场景，能帮你写出更高效的容器操作代码。
核心定义与区别
这两个函数都返回迭代器，但判断逻辑不同：
- lower_bound（下界）：在
[first, last)区间内，找到第一个大于或等于 (>=) 目标值target的元素。 - upper_bound（上界）：在
[first, last)区间内，找到第一个大于 (>) 目标值target的元素。
简单来说，lower_bound 指向的是目标值的'左边界'（包含自身），而 upper_bound 指向的是'右边界'（不包含自身）。
| 函数 | 判断条件 | 定位结果 |
|---|---|---|
| lower_bound | >= target | 目标值的左边界（包含自身） |
| upper_bound | > target | 目标值的右边界（不包含自身） |
使用前提与参数说明
必须满足的前提
查找区间 [first, last) 必须是升序排列的（默认使用 < 运算符比较）。如果区间无序，函数的行为是未定义的，结果完全不可预测。这是新手最容易踩的坑，使用前务必确认数据已排序。
函数参数
以 lower_bound 为例，有两个重载版本：
- 默认比较（升序）
template <class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val); - 自定义比较（支持降序等）
template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
upper_bound 的参数格式完全相同，仅内部判断逻辑不同。
这里几个关键参数需要留意：
first/last：迭代器，指定查找的左闭右开区间[first, last)。val：要查找的目标值。comp：可选参数，自定义比较函数或谓词（例如greater<int>()可用于降序区间）。
返回值
- 成功找到：返回指向该元素的迭代器。
- 未找到：返回
last迭代器（即区间末尾的哨兵，不指向任何有效元素）。
实战用法
1. 判断目标值是否存在
利用 lower_bound 的特性，如果它返回的迭代器不等于 end()，且指向的元素确实等于目标值，那就说明存在。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 3, 5, 7, 9};
int target = 5;
auto it = lower_bound(v.begin(), v.end(), target);
if (it != v.end() && *it == target) {
cout << "目标值 " << target << " 存在" << endl;
}
return 0;
}
2. 统计重复元素出现次数
这是一个经典技巧。既然 lower_bound 指向第一个等于 target 的位置，upper_bound 指向第一个大于 target 的位置，那么两者之间的差值就是 target 出现的次数。
vector<int> v = {1, 3, 5, 5, 5, 7, 9};
int target = 5;
auto left = lower_bound(v.begin(), v.end(), target); // 指向第一个 5
auto right = upper_bound(v.begin(), v.end(), target); // 指向 7
int count = right - left; // 5 - 2 = 3，即 5 出现 3 次
cout << "目标值 " << target << " 出现次数：" << count << endl;
3. 在有序容器中插入元素
如果你有一个有序容器，想插入新元素并保持有序，直接用 lower_bound 找到位置即可，无需手动排序。
vector<int> v = {1, 3, 7, 9};
int insert_val = 5;
// 找到第一个 >= 5 的位置（即 7 之前），插入 5
auto pos = lower_bound(v.begin(), v.end(), insert_val);
v.insert(pos, insert_val);
// 插入后 v = {1, 3, 5, 7, 9}，仍保持升序
4. 处理降序区间
当区间为降序时，默认的比较逻辑会失效，需要传入 greater<> 作为比较函数。此时 lower_bound 的逻辑变为找第一个小于等于的值，upper_bound 变为找第一个小于的值。
vector<int> v_desc = {10, 8, 6, 4, 2, 1};
int target = 4;
// 找第一个 <= 4 的元素（降序中 lower_bound 逻辑变为'<='）
auto it_lower = lower_bound(v_desc.begin(), v_desc.end(), target, greater<int>());
// 找第一个 < 4 的元素（降序中 upper_bound 逻辑变为'<'）
auto it_upper = upper_bound(v_desc.begin(), v_desc.end(), target, greater<int>());
cout << "降序中 >=4 的第一个元素：" << *it_lower << endl; // 输出：4
cout << "降序中 >4 的第一个元素：" << *it_upper << endl; // 输出：2
掌握这两个函数，配合 STL 容器，能让你的二分查找逻辑既简洁又健壮。记得，有序是前提，自定义比较器是进阶必备。