C++ lower_bound()和upper_bound()函数的用法（附带实例）

C++ STL 中的 lower_bound() 和 upper_bound() 是两个用于在有序集合中进行二分查找的高效函数。它们的时间复杂度为 O(log n)，适用于快速查找特定值的位置或范围。

C++ lower_bound()函数

lower_bound() 函数返回指向第一个不小于给定值的元素的迭代器。如果所有元素都小于该值，则返回指向序列尾部的迭代器。如果存在多个相等的元素，则返回指向第一个元素的迭代器。

下面是使用 lower_bound() 函数的示例代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 5, 7, 9};      // 定义一个整数类型的向量 v，并初始化为 {1, 3, 5, 7, 9}
    int val = 5;                          // 定义一个整数变量 val，并赋值为 5
    auto it = lower_bound(v.begin(), v.end(), val);  // 使用 lower_bound() 函数查找在有序容器 v 中第一个大于或等于 val 的元素的迭代器
    if (it != v.end())                    // 如果找到了符合条件的元素
        cout << "Found at index: " << it - v.begin();  // 则输出该元素的索引（通过计算迭代器与起始迭代器的差值）
    else                                  // 如果没有找到符合条件的元素
        cout << "Not found";              // 则输出 "Not found"
    return 0;
}

程序中，auto it 是一个变量声明语句，使用 auto 关键字进行自动类型推导，它将根据右侧的初始化表达式的值来推断变量的类型。

程序执行结果为：

Found at index: 2

C++ upper_bound()函数

upper_bound() 函数返回指向第一个大于给定值的元素的迭代器。如果所有元素都不大于该值，则返回指向序列尾部的迭代器。如果存在多个等于目标值的元素，upper_bound() 函数会跳过它们，返回指向下一个大于给定值的元素。

下面是使用 upper_bound() 函数的示例代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 5, 7, 9};   // 定义一个整数类型的向量 v，并初始化为 {1, 3, 5, 7, 9}
    int val = 5;                       // 定义一个整数变量 val，并赋值为 5
    auto it = upper_bound(v.begin(), v.end(), val);  // 使用 upper_bound() 函数查找在有序容器 v 中第一个大于 val 的元素的迭代器
    if (it != v.end())                 // 如果找到了符合条件的元素
        cout << "First element greater than " << val << " is at index: " << it - v.begin();  // 则输出该元素的索引（通过计算迭代器与起始迭代器的差值）
    else                               // 如果没有找到符合条件的元素
        cout << "No elements are greater than " << val;  // 则输出 "No elements are greater than " 加上 val 的值
    return 0;                          // 返回值
}

程序的执行结果为：

First element greater than 5 is at index: 3

lower_bound() 和 upper_bound() 都假定输入范围是有序的。如果在无序的序列上使用它们，将无法保证结果正确。

lower_bound() VS upper_bound()

稍加思考，读者会发现 lower_bound() 实际上是求出给定序列的下边界，upper_bound() 是求出给定序列的是上边界。这两者遵循计算机中左闭右开的原则。

通过下表对 lower_bound() 和 upper_bound() 函数进行比较。

表：lower_bound()和upper_bound()函数的比较

函数	lower_bound()	upper_bound()
功能	查找第一个不小于给定值的元素	查找第一个大于给定值的元素
返回值	迭代器	迭代器
条件要求	输入的序列必须是有序的	输入的序列必须是有序的
时间复杂度	O(log n)	O(log n)
返回元素条件	大于或等于给定值的第一个元素	大于给定值的第一个元素
返回值为 end 的条件	所有元素都小于给定值	所有元素都小于或等于给定值