C++ lower_bound怎么用 C++二分查找第一个大于等于元素位置【算法】

2026-01-31 00:00:00 作者：裘德小鎮的故事

lower_bound返回第一个不小于给定值的迭代器；它执行二分查找，要求容器升序且支持随机访问，使用前必须检查是否等于end()以防解引用崩溃。

lower_bound 是什么，它到底返回什么

lower_bound 不是“找某个值”，而是“找第一个不小于给定值的位置”——即第一个满足 !(element 的迭代器。它不保证元素等于 value，只保证它不比 value 小。如果所有元素都小于 value，它返回末尾迭代器（比如 v.end()），这时解引用会崩溃。

常见误用：以为它一定找到相等的元素，结果拿到 v.end() 还直接 *it，触发未定义行为。

使用前必须确保容器已升序排列（默认比较规则下），否则结果无意义。它底层是二分查找，要求随机访问迭代器，所以 vector、array、deque 可用，list 或 forward_list 不能直接用。

基本用法和必须检查的边界

调用形式统一为：lower_bound(first, last, value)，其中 first 和 last 是左闭右开区间。

vector v = {1, 2, 2, 3, 4, 4, 4, 5};
auto it = lower_bound(v.begin(), v.end(), 4);
if (it != v.end()) {
    cout << "位置: " << (it - v.begin()) << ", 值: " << *it << "\n"; // 输出 4, 4
}

it 指向第一个 4（索引 4），不是任意一个 4
如果查 6，it == v.end()，此时不能解引用
如果查 0，it == v.begin()，合法

别省略 it != container.end() 判断——这是最常漏掉的安全检查。

自定义比较函数怎么写才不翻车

当容器不是基础类型，或你想按别的规则排序（比如降序、按结构体字段），必须传第三个参数，且要和排序时用的比较逻辑完全一致。

vector> v = {{3,"a"}, {1,"b"}, {1,"c"}, {2,"d"}};
sort(v.begin(), v.end()); // 默认按 first 升序
auto it = lower_bound(v.begin(), v.end(), make_pair(1, ""), 
                      [](const auto& a, const auto& b) { return a.first < b.first; });

比较函数必须是「严格弱序」：a 为真时，b 必须为假；传递性也要成立
如果你用 sort(v.begin(), v.end(), greater) 降序排，那 lower_bound 也得传 greater，否则行为未定义
lambda 捕获列表为空即可，不要捕获局部变量后又在别处调用——lower_bound 内部会多次调用它

和 upper_bound、equal_range 的关键区别

lower_bound 找第一个 ≥，upper_bound 找第一个 >，两者夹出来的区间就是所有等于目标值的元素范围。

auto l = lower_bound(v.begin(), v.end(), 2);
auto u = upper_bound(v.begin(), v.end(), 2);
// [l, u) 就是所有值为 2 的元素

equal_range(value) 直接返回 pair，等价于 {lower_bound(...), upper_bound(...)}，少写两行但多一次遍历（内部仍调两次二分）
如果你只需要判断是否存在，用 binary_search 更语义清晰，它只返回 bool，不暴露位置
不要用 lower_bound + *it == value 来判断存在性——先做指针检查再比较，否则 it == end() 时解引用就崩了