C++：upper_bound

基本用法

upper_bound 函数在 C++ 中用于在有序范围内查找大于给定值的第一个元素。这个函数属于 <algorithm> 头文件。它使用二分查找算法，因此效率较高。基本语法如下：

1	upper_bound(ForwardIterator first, ForwardIterator last, const T& val);

first 和 last 是定义待搜索区间的迭代器。
val 是我们要查找的值。

函数返回一个指向找到的元素的迭代器，如果没有找到，则返回 last。

特点和注意事项

时间复杂度: upper_bound 的时间复杂度是 O(log n)，其中 n 是 $[first, last)$ 范围内元素的数量。
要求有序: 使用 upper_bound 前，确保范围 $[first, last)$ 已排序。
返回值: 如果范围内所有元素都小于或等于 val，则返回 last。
自定义比较: 可以提供自定义比较函数。

示例代码

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

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

    // 查找第一个大于 4 的元素
    auto it = std::upper_bound(v.begin(), v.end(), 4);

    if (it != v.end()) {
        std::cout << "The first element greater than 4 is: " << *it << std::endl;
    } else {
        std::cout << "No element greater than 4 found." << std::endl;
    }

    return 0;
}

在此例中，upper_bound 会返回指向值 5 的迭代器，因为 5 是数组中第一个大于 4 的元素。

当然upper_bound和sort一样还可以自定义比较的内容，下面是另外一个例子：

取自2023-12-08 Leetcode 每日一题解法

class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        sort(rides.begin(),rides.end(), [](const vector<int> &a, const vector<int> &b){
            if(a[1]==b[1])return a[0] < b[0];
            return a[1] < b[1];
        });
        int p_num = rides.size();
        vector<long long> dp(p_num+1);
        for(int i=0;i<p_num;++i){
            int j = upper_bound(rides.begin(), rides.begin() + i, rides[i][0], [](int x, const vector<int> &r){
                return x < r[1];
            }) - rides.begin();
            dp[i+1] = max(dp[i], dp[j]+rides[i][1]-rides[i][0]+rides[i][2]);
        }
        return dp[p_num];
    }
};

该内嵌自定义匿名函数主要实现了告知upper_bound函数如何将传入的整数和vector中的vector类型比较大小。