lower_bound

在 C++ 中，<algorithm> 头文件中的lower_bound 函数是一个非常有用的算法，它用于在已排序的范围内查找第一个不小于给定值的元素。下面我将详细解释这个函数的基本用法、特点和注意事项，以及提供示例代码。

基本用法

• 函数原型：lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
• 参数：
  • first 和 last 是定义要搜索的范围的迭代器。
  • val 是我们要查找的值。
• 返回值：指向范围中第一个不小于 val 的元素的迭代器。如果所有元素都小于 val，则返回 last。

特点和注意事项

• lower_bound 需要预排序的范围。如果范围没有排序，结果是未定义的。
• 它使用二分查找算法，因此时间复杂度为 O(log n)，其中 n 是范围内元素的数量。
• 如果范围中存在多个等于 val 的元素，lower_bound 会返回指向这些元素中第一个的迭代器。
• 对于自定义类型，你可能需要提供比较函数或重载比较操作符。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 6, 7};

    // 查找第一个不小于4的元素
    auto it = std::lower_bound(vec.begin(), vec.end(), 4);

    if (it != vec.end()) {
        std::cout << "第一个不小于4的元素是: " << *it << std::endl;
    } else {
        std::cout << "没有找到不小于4的元素" << std::endl;
    }

    return 0;
}

在这个例子中，我们在一个已排序的 vector 中查找第一个不小于4的元素。由于集合中有两个4，lower_bound 返回指向第一个4的迭代器。