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

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。

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

示例：

PIA

全面的AI聚合平台，一站式访问所有顶级AI模型

226 查看详情 PIA

#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 可找出某个值的范围。

示例：

PIA

全面的AI聚合平台，一站式访问所有顶级AI模型

226 查看详情 PIA

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的详细内容，更多请关注知识资源分享宝库其它相关文章！

相关标签： go ai c++ ios Array 结构体 int Lambda map 算法大家都在看： Golang的包管理机制如何运作介绍go mod的依赖管理方式 C++和Go之间有哪些区别？ C++井字棋AI实现简单决策算法编写如何为C++搭建边缘AI训练环境 TensorFlow分布式训练配置怎样用C++开发井字棋AI 简单决策算法实现方案