C++中lower_bound 与 upper_bound 函数详解
目录
lower_bound 和 upper_bound 是 C++ 标准库 <algorithm> 头文件中的二分查找算法，专门用于在有序区间中高效定位元素
一.核心定义与核心区别
函数的头文件： #include <algorithm>
lower_bound（下界函数）
功能：在 [first, last) 区间内，找到第一个大于或等于（≥）目标值 target 的元素，返回其迭代器。
upper_bound（上界函数）
功能：在 [first, last) 区间内，找到第一个大于（＞）目标值 target 的元素，返回其迭代器。
函数 | 判断条件 | 定位结果 |
lower_bound | ≥ target | 目标值的“左边界”（包含自身） |
upper_bound | ＞ target | 目标值的“右边界”（不包含自身） |
二.使用前提与参数说明
1. 必须满足的前提
- 查找区间 [first, last) 必须是升序排列的（默认使用 < 运算符比较）。
- 若区间无序，函数行为未定义（结果不可预测）
2. 函数参数
1. 默认比较（升序，使用 < 运算符）
template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);2. 自定义比较（升序，可传入自定义规则，如 greater<int>() 实现降序查找）
template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);upper_bound 参数格式完全相同，仅判断逻辑不同
- ForwardIterator就是一个迭代器，如vector< int > v，v数组的首元素就是 v.begin()
- T&val , 就是一个T类型的变量
- Compare 就是一个比较器，可以传仿函数对象，也可以传函数指针
- first/last：迭代器，指定查找的左闭右开区间 [first, last)
- val：要查找的目标值
- comp：可选参数，自定义比较函数/谓词（如 greater<int>() 用于降序区间）
3.返回值
- 成功找到符合条件的元素：返回指向该元素的迭代器
- 未找到（所有元素都不满足条件）：返回 last 迭代器（区间末尾的“哨兵”，不指向任何有效元素）
三.用法
（1）判断目标值是否存在
若 lower_bound 返回的迭代器不等于 last，且该迭代器指向的元素 等于 target，则 target 存在
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; // 输出：目标值 5 存在 }（2）计算目标值的出现次数（统计重复元素）
upper_bound 与 lower_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（索引 2） auto right = upper_bound(v.begin(), v.end(), target); // 指向 7（索引 5） 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<> 作为比较函数
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 
