C++算法

C++ 中 lower_bound 与 upper_bound 核心用法

C++ STL 中的 lower_bound 与 upper_bound 是基于二分查找的核心工具。lower_bound 返回第一个不小于目标值的迭代器，upper_bound 返回第一个大于目标值的迭代器。两者均要求序列有序，时间复杂度为 O(log n)。常用于确定插入位置、统计元素频次及检查存在性。使用时需注意比较函数与序列排序规则的一致性，并验证迭代器是否越界。

Pythonist发布于 2026/3/27更新于 2026/9/1160 浏览

C++ 中 lower_bound 与 upper_bound 核心用法

C++ 中 lower_bound 与 upper_bound 核心用法

核心定义与区别

在有序序列里找位置，这两个函数是标配。理解它们的返回值逻辑，能避免很多低级错误。

lower_bound 作用：找到第一个不小于目标值的元素。返回值：如果找到了，返回该元素的迭代器；没找到，返回第一个比它大的元素位置。比如 {1,2,4,4,5} 找 4，返回索引 2（第一个 4）。

upper_bound 作用：找到第一个大于目标值的元素。返回值：如果找到了，返回最后一个匹配元素的下一个位置；没找到，行为同 lower_bound。同样序列找 4，返回索引 4（数字 5 的位置）。

特性	lower_bound	upper_bound
等价元素处理	指向第一个等价元素	指向最后一个等价元素的下一个位置
插入位置	插入后位于相同元素之前	插入后位于相同元素之后
目标值不存在时返回值	第一个大于目标值的元素位置	同上

使用条件与时间复杂度

前提很简单：序列必须已排序。升序或按自定义规则有序都行，要是乱序调用，结果未定义，别问为什么问了就是 UB。

时间复杂度都是 O(log n)，底层基于二分查找，效率很高。

实际应用场景

保持有序插入 往容器里塞新数据，想维持顺序，直接算出位置插进去就行。

auto pos = upper_bound(v.begin(), v.end(), new_value);
v.insert(pos, new_value); // 插入后序列仍有序

自定义排序规则 默认是按 < 比较，复杂点的数据结构可以传比较函数。

// 按个位数排序的数组
bool cmp(int a, int b) {
    return a % 10 < b % 10;
}
auto it = lower_bound(arr, arr + n, 36, cmp); // 查找个位数 >=6 的第一个元素

统计出现次数 利用两个函数的差值，区间跨度就是数量。

int count = upper_bound(v.begin(), v.end(), target) - lower_bound(v.begin(), v.end(), target);

auto it = lower_bound(v.begin(), v.end(), target);
bool exists = (it != v.end()) && (*it == target);

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> v = {1, 2, 4, 4, 5, 7, 8};
    int target = 4;

    // lower_bound 示例
    auto low = lower_bound(v.begin(), v.end(), target);
    cout << "lower_bound 位置：" << (low - v.begin()) << "，值：" << *low << endl;
    // 输出 2, 4

    // upper_bound 示例
    auto up = upper_bound(v.begin(), v.end(), target);
    cout << "upper_bound 位置：" << (up - v.begin()) << "，值：" << *up << endl;
    // 输出 4, 5

    return 0;
}