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

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

裘德小鎮的故事

发布： 2025-11-12 16:23:29

原创

321人浏览过

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

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

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

std::lower_bound 基本用法

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

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

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

示例代码：

立即学习“C++免费学习笔记（深入）”；

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

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

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9};
    auto it = std::lower_bound(nums.begin(), nums.end(), 6);
    if (it != nums.end()) {
        std::cout << "位置: " << (it - nums.begin()) << ", 值: " << *it << "\n";
    } else {
        std::cout << "未找到符合条件的元素\n";
    }
    // 输出：位置: 3, 值: 7
    return 0;
}

自定义比较函数

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

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

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