lower_bound和upper_bound

阅读量: 30 编辑

lower_bound 和 upper_bound 是 C++ 标准库 <algorithm> 中的函数,用于在有序序列(如数组或容器)中进行二分查找。

lower_bound 函数用于查找在有序序列中第一个大于或等于给定值的元素的位置。

upper_bound 函数用于查找在有序序列中第一个大于给定值的元素的位置。

template<class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

template<class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

这两个函数在查找失败时返回的是一个迭代器,该迭代器指向有序序列中第一个大于给定值的位置。如果查找成功,则返回的迭代器指向找到的元素。

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5, 5, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 使用 lower_bound 查找第一个大于或等于 5 的元素的位置
    int* lb = lower_bound(arr, arr + n, 5);
    cout << "Lower bound position of 5: " << lb - arr << endl;//4

    // 使用 upper_bound 查找第一个大于 5 的元素的位置
    int* ub = upper_bound(arr, arr + n, 5);
    cout << "Upper bound position of 5: " << ub - arr << endl;//7

    return 0;
}

爱码岛编程公众号
微信扫码关注
爱码岛编程小程序
微信扫码打开
苏ICP备13052010号
©2023 南京匠成信息科技有限公司