在C++的STL中，lower_bound和upper_bound是基于二分查找的两个算法函数，定义在头文件algorithm里。它们都要求操作的范围已经按照升序排好序，用来在有序序列中快速找到特定的边界位置。理解这两个函数对于处理有序数据非常重要。
基本含义与区别
对于一个有序区间，假设我们要查找值x：
- lower_bound：返回指向第一个不小于x的元素的迭代器，也就是第一个大于等于x的位置。
- upper_bound：返回指向第一个大于x的元素的迭代器，也就是第一个严格大于x的位置。
如果找不到对应元素，它们都会返回尾迭代器end()。利用这两个函数，我们可以很方便地算出某个值出现了多少次。
在vector中的基础用法
下面代码展示如何在int类型的vector里使用这两个函数：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 2, 2, 3, 4, 5};
int x = 2;
// 找到第一个大于等于x的位置
auto low = std::lower_bound(v.begin(), v.end(), x);
// 找到第一个大于x的位置
auto up = std::upper_bound(v.begin(), v.end(), x);
std::cout << "lower_bound index: " << (low - v.begin()) << std::endl;
std::cout << "upper_bound index: " << (up - v.begin()) << std::endl;
// 统计x出现的次数
int count = up - low;
std::cout << "count of " << x << ": " << count << std::endl;
return 0;
}
上面例子中，lower_bound指向索引1，upper_bound指向索引4，二者相减得到2出现了3次。
使用自定义比较函数
如果容器里存的是自定义结构，或者需要降序排列，就要传一个比较函数。注意比较函数要和序列的排序规则一致。
#include <iostream>
#include <vector>
#include <algorithm>
struct Node {
int val;
};
// 按val降序排列时的比较：a应该排在b前面返回true
bool cmp(const Node& a, const Node& b) {
return a.val > b.val;
}
int main() {
std::vector<Node> v = {{5}, {4}, {4}, {2}};
Node target = {4};
// 序列按cmp降序排好，查找时也要用同样的cmp
auto low = std::lower_bound(v.begin(), v.end(), target, cmp);
auto up = std::upper_bound(v.begin(), v.end(), target, cmp);
std::cout << "lower index: " << (low - v.begin()) << std::endl;
std::cout << "upper index: " << (up - v.begin()) << std::endl;
return 0;
}
常见注意事项
| 注意点 | 说明 |
|---|---|
| 区间必须有序 | 如果无序，结果是未定义的，可能找不到正确位置 |
| 时间复杂度 | 都是O(log n)，比线性查找快很多 |
| 返回类型 | 返回迭代器，不是下标，需要用减法得到索引 |
总的来说，lower_bound和upper_bound是STL里处理有序数据的利器。只要保证序列有序并理解“不小于”和“大于”的差别，就能在项目中灵活使用它们来提升查询效率。
C++STLlower_boundupper_boundbinary_search修改时间：2026-07-25 02:54:19