lower_bound

https://www.geeksforgeeks.org/lower_bound-in-cpp/

在有序数组中，找到大于或等于目标值的数据集合中值最小的位置。

The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number. If there are multiple values that are equal to val, lower_bound() returns the iterator of the first such value.
The elements in the range shall already be sorted or at least partitioned with respect to val.

// CPP program to illustrate
// std :: lower_bound
#include <bits/stdc++.h>

// Driver code
int main()
{
    // Input vector
    std::vector<int> v{ 10, 20, 30, 30, 30, 40, 50 };

    // Print vector
    std::cout << "Vector contains :";
    for (unsigned int i = 0; i < v.size(); i++)
        std::cout << " " << v[i];
    std::cout << "\n";

    std::vector<int>::iterator low1, low2, low3;
    
    // std :: lower_bound
    low1 = std::lower_bound(v.begin(), v.end(), 30);
    low2 = std::lower_bound(v.begin(), v.end(), 35);
    low3 = std::lower_bound(v.begin(), v.end(), 55);

    // Printing the lower bounds
    std::cout
        << "\nlower_bound for element 30 at position : "
        << (low1 - v.begin());
    std::cout
        << "\nlower_bound for element 35 at position : "
        << (low2 - v.begin());
    std::cout
        << "\nlower_bound for element 55 at position : "
        << (low3 - v.begin());

    return 0;
}

Vector contains : 10 20 30 30 30 40 50

lower_bound for element 30 at position : 2
lower_bound for element 35 at position : 5
lower_bound for element 55 at position : 7

upper_bound

https://www.geeksforgeeks.org/upper_bound-in-cpp/

在有序数组中，找到大于目标值的数据集合中值最小的位置。

upper_bound() is a standard library function in C++ defined in the header . It returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to val.

// CPP program to illustrate using
// std :: upper_bound with vectors
#include <bits/stdc++.h>

// Driver code
int main()
{
    std::vector<int> v{ 10, 20, 30, 40, 50 };

    // Print vector
    std::cout << "Vector contains :";
    for (int i = 0; i < v.size(); i++)
        std::cout << " " << v[i];
    std::cout << "\n";

    std::vector<int>::iterator upper1, upper2;

    // std :: upper_bound
    upper1 = std::upper_bound(v.begin(), v.end(), 35);
    upper2 = std::upper_bound(v.begin(), v.end(), 45);

    std::cout << "\nupper_bound for element 35 is at position : "
            << (upper1 - v.begin());
    std::cout << "\nupper_bound for element 45 is at position : "
            << (upper2 - v.begin());

    return 0;
}

Vector contains : 10 20 30 40 50
upper_bound for element 35 is at position : 3
upper_bound for element 45 is at position : 4

分析

https://whiteboard-online.org/boards/j2YHktkNiGeLZJH4xt60jHKOXgozBdBdLjagR2-vdRY-

有序数组

如果查找的目标值在数组中， 例如下图中x=20， 那么 lower_bound定位到第一个目标值（第一个20）， upper_bound定位到第一个大于20数位置（30）

如果查找的目标值不在数组中， 例如下图中x=25， 那么 lower_bound定位到30， upper_bound也定位到30，

　　lower_bound关注的是>=x, upper_bound关注的是>x， 这时（x不在数组中），lower_bound退化为upper_bound.