lower_bound()和upper_bound()有什么用处？
lower_bound() 和 upper_bound() 是 C++ STL 中用于在已排序的范围内进行二分搜索的两个函数。它们的作用是找到一个范围内不小于（或不大于）某个给定值的第一个元素的位置。这两个函数通常用于有序序列，尤其是在处理有重复元素时非常有用。
lower_bound():- 返回一个迭代器，指向在不破坏顺序的情况下，可以插入给定值的第一个位置，而不让任何原有的元素小于给定值。
- 如果序列中存在与给定值相等的元素，
lower_bound()会返回指向这些元素中第一个的迭代器。 - 如果所有元素都小于给定值，则返回指向序列尾部的迭代器。
upper_bound():- 返回一个迭代器，指向在不破坏顺序的情况下，可以插入给定值的最后一个位置，而不让任何原有的元素小于或等于给定值。
- 如果序列中存在与给定值相等的元素，
upper_bound()会返回指向这些元素中最后一个之后的迭代器。 - 如果所有元素都小于或等于给定值，则返回指向序列尾部的迭代器。
应用场景示例
假设你有一个已排序的 vector<int>，其中包含重复元素，并且你想找到一个特定值的范围：
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 4, 4, 4, 5, 6};
// 寻找不小于4的第一个元素的位置
auto lower = std::lower_bound(v.begin(), v.end(), 4);
std::cout << "Lower bound for 4 is at index: " << (lower - v.begin()) << std::endl;
// 寻找大于4的第一个元素的位置
auto upper = std::upper_bound(v.begin(), v.end(), 4);
std::cout << "Upper bound for 4 is at index: " << (upper - v.begin()) << std::endl;
return 0;
}
在这个例子中，lower_bound() 将返回指向第一个 4 的迭代器，而 upper_bound() 将返回指向最后一个 4 之后的位置的迭代器。这样你就可以得到等于 4 的所有元素的范围，即 [lower, upper)。这在统计有序序列中等于某个值的元素数量时非常有用。