c++如何使用std::lower_bound进行二分查找_C++在有序序列中高效查找方法

std::lower_bound用于在有序序列中查找第一个不小于目标值的元素位置，返回迭代器。支持自定义比较函数，适用于升序（默认）和降序（如配合std::greater）场景。与std::upper_bound和std::binary_search结合可实现范围查询和存在性判断。其时间复杂度为O(log n)，是高效安全的二分查找工具。

在C++中，std::lower_bound 是一个非常高效的二分查找工具，适用于已排序的序列，可以在对数时间内找到第一个不小于给定值的元素位置。

std::lower_bound 基本用法

该函数定义在 algorithm 头文件中，用于在有序区间内查找满足条件的第一个位置。其基本语法如下：

std::lower_bound(起始迭代器, 结束迭代器, 目标值)

返回一个迭代器，指向第一个大于等于目标值的元素。如果所有元素都小于目标值，则返回尾后迭代器（end）。

示例代码：

#include
#include
#include iostream>

int main() {
    std::vector nums = {1, 3, 5, 7, 9};
    auto it = std::lower_bound(nums.begin(), nums.end(), 6);
    if (it != nums.end()) {
        std::cout     } else {
        std::cout     }
    // 输出：位置: 3, 值: 7
    return 0;
}

自定义比较函数

若容器中的元素类型复杂，或需要改变比较逻辑，可以传入自定义比较函数或lambda表达式。例如，在降序序列中查找：

std::vector desc = {10, 8, 6, 4, 2};
auto it = std::lower_bound(desc.begin(), desc.end(), 5, std::greater // 使用 greater 实现降序下的“lower_bound”

此时查找的是在降序排列中，第一个小于等于目标值的位置，保持语义一致。

与 std::upper_bound 和 std::binary_search 的区别

• std::lower_bound：找第一个 ≥ value 的位置
• std::upper_bound：找第一个 > value 的位置
• std::binary_search：仅判断 value 是否存在，返回 bool

三者结合可实现精确范围查找，比如统计某个值出现次数：

int count = std::upper_bound(nums.begin(), nums.end(), target)
    - std::lower_bound(nums.begin(), nums.end(), target);

基本上就这些。只要数据有序，std::lower_bound 就能以 O(log n) 时间完成定位，是替代手写二分查找的首选方法，既安全又高效。