lower_bound和upper_bound

lower_bound 和 upper_bound 是 C++ 标准库中的函数，用于在有序序列（如数组或容器）中进行二分查找。

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

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

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

template
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;
}

经典算法

lower_bound和upper_bound