std::lower_bound 是 C++ 标准库中用于在有序序列中查找元素的重要函数，位于 <algorithm> 头文件中。它通过二分查找高效定位目标值的插入位置，适用于已排序的容器（如 vector、array 等）。以下是详细解析：

函数原型与参数

// 版本1：使用<运算符比较
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

// 版本2：使用自定义比较函数comp
template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

• 参数说明：
  • first, last：指向有序序列的迭代器范围（左闭右开区间 [first, last)）。
  • value：要查找的目标值。
  • comp（可选）：自定义比较函数，需满足 comp(a, b) 为真时表示 a 应排在 b 前面。

功能与返回值

• 功能：在有序序列中查找第一个 不小于 value 的元素位置。
• 返回值：迭代器指向满足 value <= *it 的第一个元素；若所有元素都小于 value，则返回 last。

使用场景与示例

1. 基础用法（升序序列）

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

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9, 11};
    int target = 6;
    
    auto it = std::lower_bound(nums.begin(), nums.end(), target);
    if (it != nums.end()) {
        std::cout << "第一个不小于 " << target << " 的元素是 " << *it << std::endl;
        std::cout << "索引位置：" << (it - nums.begin()) << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }
    // 输出：第一个不小于 6 的元素是 7，索引位置：3
}

2. 降序序列与自定义比较

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

int main() {
    std::vector<int> nums = {11, 9, 7, 5, 3, 1}; // 降序排列
    int target = 6;
    
    // 使用自定义比较函数（降序时需反转比较逻辑）
    auto it = std::lower_bound(nums.begin(), nums.end(), target, 
                              [](int a, int b) { return a > b; });
    
    if (it != nums.end()) {
        std::cout << "降序中第一个不小于 " << target << " 的元素是 " << *it << std::endl;
    }
    // 输出：降序中第一个不小于 6 的元素是 7
}

3. 结构体与自定义类型

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

struct Person {
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
};

// 自定义比较：按年龄升序
bool compareAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

int main() {
    std::vector<Person> people = {
        {"Alice", 25}, {"Bob", 30}, {"Charlie", 28}, {"David", 35}
    };
    Person target("", 28); // 查找年龄不小于28的第一个人
    
    auto it = std::lower_bound(people.begin(), people.end(), target, compareAge);
    if (it != people.end()) {
        std::cout << "第一个年龄不小于28的人：" << it->name << "，年龄：" << it->age << std::endl;
    }
    // 输出：第一个年龄不小于28的人：Charlie，年龄：28
}

与其他查找函数的对比

注意事项

1. 序列必须有序：若输入序列未排序，lower_bound 的行为未定义。
2. 迭代器要求：至少为前向迭代器（ForwardIt），但随机访问迭代器（如 vector::iterator）能优化二分查找的性能。
3. 返回值含义：
   • 若 value 存在，lower_bound 返回其首次出现的位置；
   • 若 value 不存在，返回其应插入的位置（保持序列有序）。
4. 自定义比较的一致性：使用 comp 时，需确保比较逻辑与容器排序规则一致（如降序序列需传递反转的比较函数）。

典型应用

• 插入位置计算：在有序容器中插入元素时，用 lower_bound 确定插入点以保持有序性：

  nums.insert(std::lower_bound(nums.begin(), nums.end(), 6), 6);
  

• 二分查找变种：如查找第一个大于等于目标值的元素、统计不小于目标值的元素数量等。
• 高效去重：配合 unique 函数，先排序再用 lower_bound 过滤重复元素。

通过合理使用 std::lower_bound，可在有序序列中实现高效的查找与插入操作，避免线性遍历的性能损耗。