c++ lower_bound用法_c++二分查找第一个大于等于的值

发布日期： 2026-01-19 阅读量： 作者： 冰火之心

lower_bound用于在升序区间查找首个≥target元素的迭代器，需配合!=end()判断存在性，时间复杂度O(log n)，误用常见于未排序数据、越界或类型不匹配。

lower_bound 查找第一个 ≥ target 的位置

lower_bound 是 C++ 标准库中用于二分查找的函数，作用是在已排序的区间内找到第一个不小于 target（即 ≥ target）的元素迭代器。它要求输入范围必须是升序排列，否则行为未定义。

常见误用是把它当成“查找是否存在”，其实它只返回位置；若要判断存在性，得配合 != end() 检查。

头文件：#include
适用容器：所有支持随机访问迭代器的有序序列，如 std::vector、std::array、原生数组
时间复杂度：O(log n)，比手写循环或线性查找快得多
注意：不是 std::set::lower_bound —— 后者是成员函数，接口和性能略有不同

基本调用形式与参数含义

最常用重载签名是：

std::lower_bound(first
, last, value)

其中：

first 和 last 是左闭右开区间，比如 v.begin(), v.end()
value 是待查找的目标值，类型需能与容器元素比较（通常要求 operator 可用）
返回值是迭代器，指向第一个满足 *it >= value 的位置；若不存在，返回 last

如果自定义比较逻辑（比如降序或结构体字段），需传入第 4 个参数：comp，例如：

std::lower_bound(v.begin(), v.end(), x, [](int a, int b) { return a > b; }); // 降序下的 lower_bound

常见错误：越界、未排序、类型不匹配

这三个问题占实际调试中 80% 以上的 lower_bound 故障：

对未排序数据调用 → 结果不可预测，可能返回任意位置（不是报错！）
用 std::lower_bound(arr, arr + n, x) 但 n == 0 → 返回 arr + 0，解引用前必须检查是否等于 last
容器元素是 pair，却直接传 int 值查找 → 编译失败，因为无法隐式转换；应传 pair 或自定义比较器
用 std::lower_bound 查 std::set → 虽然能编译，但效率差（O(n) 迭代器移动），应改用 s.lower_bound(x)

获取下标、判断存在、避免崩溃的惯用写法

实际工程中，几乎从不直接解引用返回的迭代器，而是先转下标或判空：

auto it = std::lower_bound(v.begin(), v.end(), x);
if (it != v.end()) {
    size_t pos = it - v.begin(); // 安全获得下标
    std::cout << "found at index " << pos << "\n";
} else {
    std::cout << "not found\n";
}

更紧凑的写法（尤其在算法题中）：

int pos = std::lower_bound(v.begin(), v.end(), x) - v.begin();
if (pos < v.size() && v[pos] == x) { /* 找到精确匹配 */ }

注意：仅当需要「等于」时才检查 v[pos] == x；lower_bound 本身只保证 ≥，不保证相等。

边界情况最容易被忽略的是空容器和全小于 target 的情况——这两种都返回 end()，必须统一处理，不能假设一定有结果。

上一篇: Blazor 怎么处理按钮点击事件

下一篇: iPhone 14如何优化键盘输入体验

c++ lower_bound用法_c++二分查找第一个大于等于的值

随便看看

南昌壹佳企网络通信有限公司