Upper bound和lower bound

2024-01-08 20:30:04

使用 upper_boundlower_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);
}

注意 pq 的返回值类型为迭代器

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

  • 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);


}

文章来源:https://blog.csdn.net/qq_44458671/article/details/135464560
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。