C++中lower_bound怎么用？如何实现二分查找第一个大于等于目标值

lower_bound是C++标准库中提供的二分查找算法，核心作用是在有序序列中查找第一个大于等于目标值的元素位置，相比手动实现二分查找，它的使用更简洁且不易出错，是处理有序序列查找需求的常用工具。

lower_bound的基本语法

lower_bound属于<algorithm>头文件，它的常用函数原型有两种形式，开发者可以根据是否需要自定义比较规则选择使用。

默认比较规则版本

该版本使用<运算符进行比较，要求序列元素支持小于比较操作，函数原型如下：

// 返回第一个大于等于value的元素迭代器
// first和last是查找范围的迭代器，左闭右开区间[first, last)
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

自定义比较规则版本

如果需要自定义比较逻辑，比如按照元素的某个成员变量排序，可以使用带比较器的版本：

// comp是比较函数，满足comp(a,b)返回true表示a排在b前面
template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

lower_bound的使用示例

下面通过几个常见场景展示lower_bound的实际用法，所有示例的前提是操作的序列已经是升序排列的。

在普通数组中使用

普通数组可以通过指针作为迭代器传入lower_bound，示例代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 6;
    // 查找第一个大于等于6的元素位置
    int* pos = lower_bound(arr, arr + n, target);
    if (pos != arr + n) {
        cout << "找到第一个大于等于" << target << "的元素是：" << *pos << endl;
        // 计算下标
        int index = pos - arr;
        cout << "元素下标是：" << index << endl;
    } else {
        cout << "没有找到大于等于" << target << "的元素" << endl;
    }
    return 0;
}

上述代码中，数组是升序的，target为6，第一个大于等于6的元素是7，对应的下标是3，程序会输出对应的结果。

在vector容器中使用

vector是常用的动态数组容器，使用lower_bound的示例如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {2, 4, 6, 8, 10};
    int target = 5;
    // 使用vector的begin和end迭代器作为查找范围
    auto it = lower_bound(nums.begin(), nums.end(), target);
    if (it != nums.end()) {
        cout << "第一个大于等于" << target << "的元素是：" << *it << endl;
    }
    return 0;
}

自定义比较规则的使用

如果序列是按照自定义的规则排序的，比如存储的是结构体，按照结构体的某个字段升序排列，就需要传入自定义比较器：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Student {
    int score;
    string name;
};

int main() {
    vector<Student> students = {{60, "张三"}, {75, "李四"}, {85, "王五"}, {90, "赵六"}};
    // 按照分数升序排列，已经在定义时有序
    int target_score = 80;
    // 自定义比较规则：按Student的score字段比较
    auto comp = [](const Student& s, int val) -> bool {
        return s.score < val;
    };
    auto it = lower_bound(students.begin(), students.end(), target_score, comp);
    if (it != students.end()) {
        cout << "第一个分数大于等于" << target_score << "的学生是：" << it->name << "，分数：" << it->score << endl;
    }
    return 0;
}

lower_bound的底层实现逻辑

lower_bound的核心实现就是二分查找，下面用简化的代码模拟它的实现过程，帮助理解其查找第一个大于等于值的逻辑：

#include <iostream>
#include <vector>
using namespace std;

// 模拟lower_bound的默认实现
template<class ForwardIt, class T>
ForwardIt my_lower_bound(ForwardIt first, ForwardIt last, const T& value) {
    ForwardIt left = first;
    ForwardIt right = last;
    while (left < right) {
        // 计算中间位置，避免溢出
        ForwardIt mid = left + (right - left) / 2;
        if (*mid < value) {
            // 中间值小于目标值，说明目标在右半部分
            left = mid + 1;
        } else {
            // 中间值大于等于目标值，可能是结果，继续向左查找更小的符合条件的位置
            right = mid;
        }
    }
    return left;
}

int main() {
    vector<int> nums = {1, 3, 5, 7, 9};
    int target = 5;
    auto it = my_lower_bound(nums.begin(), nums.end(), target);
    if (it != nums.end()) {
        cout << "第一个大于等于" << target << "的元素是：" << *it << endl;
    }
    return 0;
}

上述模拟实现中，当中间值小于目标值时，左边界右移；否则右边界左移，最终左边界的位置就是第一个大于等于目标值的元素位置，和lower_bound的行为一致。

使用lower_bound的注意事项

• 查找的序列必须是升序有序的，如果序列无序，lower_bound的结果是未定义的，不会报错但会得到错误结果。
• 返回的是迭代器，如果找不到大于等于目标值的元素，会返回last迭代器，使用前需要判断是否为结束迭代器。
• 时间复杂度是O(log n)，n是查找范围的元素数量，比线性查找效率更高，适合处理大规模有序序列。
• 如果序列是降序排列的，需要传入自定义的比较规则，比如使用greater<int>()作为比较器，此时查找的是第一个小于等于目标值的元素。

与upper_bound的区别

和lower_bound经常一起使用的是upper_bound，两者的区别如下：

比如序列是{1,3,3,5}，查找target=3，lower_bound返回第一个3的位置，upper_bound返回5的位置，开发者可以根据实际需求选择对应的算法。

lower_bound二分查找STL算法C++算法修改时间：2026-06-24 01:30:52