Cpp-STL-lower_bound和upper_bound高级用法

基本用法

我们都知道C++ STL中有两个函数lower_bound和upper_bound，它们都是在有序序列中进行二分查找的，lower_bound返回的是第一个大于等于给定值的元素的位置，upper_bound返回的是第一个大于给定值的元素的位置。

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

using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    cout << *lower_bound(v.begin(), v.end(), 5) << endl;    // 5
    cout << *upper_bound(v.begin(), v.end(), 5) << endl;    // 6
    return 0;
}

上面是最简单的用法，其实lower_bound和upper_bound有4个参数，上面使用的是默认的cmp,但是有的时候我们可能需要针对特定问题来定义我们自己的比较方式,或者我们想要使用一个没有默认cmp的类型，那么就需要用到自定义cmp了。

自定义cmp

假如我们现在想对一个二维数组进行二分查找，那么我们就需要自定义一个cmp函数，这个函数的参数是两个vector<int>，返回值是bool

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

int main()
{
    vector<vector<int>> v = {{1, 2}, {3, 4}, {5, 6}};
    cout << *lower_bound(v.begin(), v.end(), vector<int>{3, 4}, [](vector<int> a, vector<int> b) {
        return a[0] < b[0];
    })[0] << endl;    // 3
    cout << *upper_bound(v.begin(), v.end(), vector<int>{3, 4}, [](vector<int> a, vector<int> b) {
        return a[0] < b[0];
    })[0] << endl;    // 5
    return 0;
}

上面自定义了一个比较函数，这个函数的参数是两个vector<int>，返回值是bool，这个函数的作用是比较两个vector<int>的第一个元素的大小，那么该二分查找就是对vector的第一个元素进行二分查找。

进阶

自定义比较函数的例子里，我们二分搜索的目标是一个vector<int>，也就是说搜索目标和被搜索的序列的类型是一样的，但是如果这里的搜索目标是一个数而不是vector呢？（即搜索目标和待搜索的序列类型不一样）

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

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

    cout << *lower_bound(v.begin(), v.end(), 3, [](vector<int> a, int b) {
        return a[0] < b;
    })[0] << endl;    // 3

    cout << *upper_bound(v.begin(), v.end(), 3, [](int a, vector<int> b) {
        return a < b[0];
    })[0] << endl;    // 5
}

可以看到我们待二分搜索序列中的每个元素类型是vector<int>,而函数中的搜索目标却是一个int。

attention

这里需要注意的是，若要使用这种方法，上面的lower_bound和upper_bound的比较器是不一样的，以上面的例子来说，lower_bound的比较器是 { return a[0] < b; }，而upper_bound的比较器是 { return a < b[0]; }，两个比较器的参数顺序以及函数体内的参数顺序刚好都是反过来的。