Upper bound和lower bound

使用 upper_bound 和 lower_bound 可以有效提升算法效率（例如二分查找的实现）

• upper_bound(begin, end, val)：对于升序排列，查找大于 val 的值
• lower_bound(begin, end, val)：对于升序排列，查找大于等于 val 的值
  例如

auto bound_test(vector<int> & vec, int val) {
    std::sort(vec.begin(), vec.end());

    auto p = upper_bound(vec.begin(), vec.end(), val);
    auto q = lower_bound(vec.begin(), vec.end(), val)
}

int main() {
    // vector<vector<int>> v = {{2,3},{4,5},{6,7},{8,9},{1,10}};
    // merge(v);
    // cout << fib(2);
    // string a = "hello";
    // string b = "ll";

    // cout << strStr(a, b);
    vector<int> v = {-2, 1, -3, 4, -1, 2, 1, -5, 4, 5};
    auto res = bound_test(v, 4);
}

注意 p，q 的返回值类型为迭代器

如果需要操作降序排列，加上一个额外的参数即可

• upper_bound(begin, end, val, greater<int>())：对于降序排列，查找大于 val 的值
• lower_bound(begin, end, val, greater<int>())：对于降序排列，查找大于等于 val 的值

auto bound_test(vector<int> &vec, int val) {
    std::sort(vec.begin(), vec.end());

    auto p = upper_bound(vec.begin(), vec.end(), val);
    auto q = lower_bound(vec.begin(), vec.end(), val);

    std::reverse(vec.begin(), vec.end());

    auto l = upper_bound(vec.begin(), vec.end(), val, greater<int>());
    auto r = lower_bound(vec.begin(), vec.end(), val, greater<int>());

}

int main() {
    // vector<vector<int>> v = {{2,3},{4,5},{6,7},{8,9},{1,10}};
    // merge(v);
    // cout << fib(2);
    // string a = "hello";
    // string b = "ll";

    // cout << strStr(a, b);
    vector<int> v = {-2, 1, -3, 4, -1, 2, 1, -5, 4, 5};
    bound_test(v, 4);


}