lower_bound()和upper_bound()有什么用处？
参考回答
std::lower_bound() 和 std::upper_bound() 是 C++ STL 中用于在已排序容器中查找元素位置的算法，它们的主要作用是返回特定元素或其插入位置的迭代器。这两个函数通常用于二分查找操作，并且它们只适用于已经排序的容器。
std::lower_bound()：- 作用：返回第一个 不小于 给定值的元素的位置（即第一个大于或等于指定值的元素的位置）。
- 容器要求：容器必须是已排序的（可以是升序或降序）。
- 返回值：返回指向第一个大于或等于给定值的元素的迭代器。如果没有找到这样的元素，返回容器的
end()。
示例：
std::vector<int> vec = {1, 3, 3, 5, 7}; auto it = std::lower_bound(vec.begin(), vec.end(), 3); std::cout << *it << std::endl; // 输出 3std::upper_bound()：- 作用：返回第一个 大于 给定值的元素的位置（即第一个大于指定值的元素的位置）。
- 容器要求：容器必须是已排序的（可以是升序或降序）。
- 返回值：返回指向第一个大于给定值的元素的迭代器。如果没有找到这样的元素，返回容器的
end()。
示例：
std::vector<int> vec = {1, 3, 3, 5, 7}; auto it = std::upper_bound(vec.begin(), vec.end(), 3); std::cout << *it << std::endl; // 输出 5
详细讲解与拓展
std::lower_bound() 和 std::upper_bound() 是基于二分查找算法实现的，时间复杂度为 O(log n)，这使得它们在查找排序数据中的元素或插入位置时非常高效。它们通常用于确定一个元素在已排序容器中的范围，或者用于查找一个元素的位置，尤其是当我们想要找到某个值的区间时。
std::lower_bound()的用法：- 该函数返回的迭代器指向的是第一个大于或等于给定值的元素。如果容器中存在多个相等的元素，
lower_bound()返回的是第一个等于该值的元素的位置。 - 这对于查找某个值的插入位置非常有用。假设你有一个已排序的数组，你想插入一个新的元素，
lower_bound()可以告诉你该元素应该插入的位置，以保持数组的有序性。
示例：
std::vector<int> vec = {1, 3, 3, 5, 7}; auto it = std::lower_bound(vec.begin(), vec.end(), 4); std::cout << *it << std::endl; // 输出 5，表示 4 应该插入在 5 之前- 该函数返回的迭代器指向的是第一个大于或等于给定值的元素。如果容器中存在多个相等的元素，
std::upper_bound()的用法：- 该函数返回的迭代器指向的是第一个大于给定值的元素。如果容器中存在多个相等的元素，
upper_bound()返回的是最后一个相等元素后面的位置。 upper_bound()在查找插入位置时非常有用。如果你想要将一个值插入到容器中，并且不想插入重复元素，可以使用upper_bound()来找到第一个比目标值大的位置，然后插入。
示例：
std::vector<int> vec = {1, 3, 3, 5, 7}; auto it = std::upper_bound(vec.begin(), vec.end(), 3); std::cout << *it << std::endl; // 输出 5，表示 4 应该插入在 3 后面- 该函数返回的迭代器指向的是第一个大于给定值的元素。如果容器中存在多个相等的元素，
- 结合使用
lower_bound()和upper_bound()查找区间：- 通过同时使用
std::lower_bound()和std::upper_bound()，我们可以很方便地找到某个值在已排序容器中的出现区间（即该值的所有出现位置）。 lower_bound()返回的是第一个等于目标值的元素的位置，upper_bound()返回的是第一个大于目标值的元素的位置。因此，lower_bound()和upper_bound()之间的区间就表示了目标值在容器中的所有出现位置。
示例：
std::vector<int> vec = {1, 3, 3, 5, 7}; auto lb = std::lower_bound(vec.begin(), vec.end(), 3); auto ub = std::upper_bound(vec.begin(), vec.end(), 3); std::cout << "Range: [" << (lb - vec.begin()) << ", " << (ub - vec.begin()) << ")" << std::endl; // 输出 "Range: [1, 3)"，表示 3 出现的范围是 [1, 3) - 通过同时使用
- 注意事项：
lower_bound()和upper_bound()都要求容器必须是已排序的。如果容器未排序，结果是未定义的。- 如果容器中没有找到目标元素，
lower_bound()会返回指向容器末尾的迭代器，而upper_bound()也会返回指向容器末尾的迭代器。
总结
std::lower_bound() 和 std::upper_bound() 是非常高效的查找算法，它们通过二分查找的方式，可以快速找到已排序容器中某个元素的插入位置或其上界。lower_bound() 查找的是第一个不小于指定值的位置，而 upper_bound() 查找的是第一个大于指定值的位置。它们在查找元素、确定插入位置或查找区间时非常有用。