C++如何在STL中使用lower_bound和upper

C++如何在STL中使用lower_bound和upper_bound

P粉602998670

发布： 2025-09-11 10:48:01

原创

336人浏览过

lower_bound查找第一个≥目标值的位置，upper_bound查找第一个>目标值的位置，二者配合可在有序序列中高效定位元素范围，常用于统计重复元素个数或插入位置，需保证序列有序且比较规则一致。

c++如何在stl中使用lower_bound和upper_bound

在C++的STL中，lower_bound 和 upper_bound 是两个非常有用的算法，常用于在有序序列中进行二分查找。它们定义在 algorithm 头文件中，适用于任何支持随机访问迭代器的容器，比如 vector、array、deque，以及 set、map 的键（自动有序）等。

lower_bound：查找第一个不小于目标值的位置

lower_bound(first, last, value) 返回一个迭代器，指向区间 [first, last) 中第一个不小于 value 的元素（即 ≥ value）。如果所有元素都小于 value，则返回 last。

常见用途：查找插入位置，或查找第一个等于或大于某个值的元素。

示例：

易森网络企业版

如果您是新用户，请直接将本程序的所有文件上传在任一文件夹下，Rewrite 目录下放置了伪静态规则和筛选器，可将规则添加进IIS，即可正常使用，不用进行任何设置；(可修改图片等)默认的管理员用户名、密码和验证码都是：yeesen系统默认关闭，请上传后登陆后台点击“核心管理”里操作如下:进入“配置管理”中的&ld

查看详情

立即学习“C++免费学习笔记（深入）”；

#include <algorithm>
#include <vector>
#include <iostream>
<p>int main() {
std::vector<int> vec = {1, 3, 5, 5, 7, 9};</p><pre class='brush:php;toolbar:false;'>auto it = std::lower_bound(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
    std::cout << "lower_bound at index: " << (it - vec.begin()) << ", value: " << *it << '\n';
}

登录后复制

}

输出：

lower_bound at index: 2, value: 5

登录后复制

upper_bound：查找第一个大于目标值的位置

upper_bound(first, last, value) 返回一个迭代器，指向区间 [first, last) 中第一个大于 value 的元素（即 > value）。如果所有元素都 ≤ value，则返回 last。

常见用途：查找上界，配合 lower_bound 可找出某个值的范围。

示例：

立即学习“C++免费学习笔记（深入）”；

auto it = std::upper_bound(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
    std::cout << "upper_bound at index: " << (it - vec.begin()) << ", value: " << *it << '\n';
}

登录后复制

输出：

upper_bound at index: 4, value: 7

登录后复制

配合使用：查找某个值的完整范围

当序列中有重复元素时，可以使用 lower_bound 和 upper_bound 找出值等于 value 的所有元素区间。

左边界：std::lower_bound(..., value)
右边界：std::upper_bound(..., value)
区间 [left, right) 内的元素都等于 value

示例：统计值为 5 的元素个数

int count = std::upper_bound(vec.begin(), vec.end(), 5) - 
            std::lower_bound(vec.begin(), vec.end(), 5);
std::cout << "Count of 5: " << count << '\n'; // 输出 2

登录后复制

自定义比较函数

如果容器中的元素是自定义类型，或你想使用不同的排序规则，可以传入比较函数或 lambda。

例如，对降序序列使用 greater<int>：

std::vector<int> desc = {9, 7, 5, 5, 3, 1};
auto it = std::lower_bound(desc.begin(), desc.end(), 5, std::greater<int>());
// 注意：比较函数必须与排序规则一致

登录后复制

对于结构体，比如按 id 排序的 vector：

struct Person {
    int id;
    std::string name;
};
<p>std::vector<Person> people = {{1,"A"}, {3,"B"}, {5,"C"}};
auto it = std::lower_bound(people.begin(), people.end(), 3,
[](const Person& p, int value) {
return p.id < value;
});</p>

登录后复制

基本上就这些。关键点是：序列必须有序，否则结果未定义；理解 lower 是 ≥，upper 是 >；合理使用可高效查找和统计。

以上就是C++如何在STL中使用lower_bound和upper_bound的详细内容，更多请关注php中文网其它相关文章！