C++ STL中lower_bound和upper_bound用法详解

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。

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

示例：

#include 
#include 
#include 
int main() {
std::vector vec = {1, 3, 5, 5, 7, 9};
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 可找出某个值的范围。

示例：

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：

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

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

struct Person {
    int id;
    std::string name;
};
std::vector 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;
});

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