lower_bound()和upper_bound()有什么用处？

八股文_C++STL面试题 0 226

参考回答

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;  // 输出 3
```
C++
std::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
```
C++

详细讲解与拓展

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 之前
```
C++
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 后面
```
C++
结合使用 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)
```
C++
注意事项：
- lower_bound() 和 upper_bound() 都要求容器必须是已排序的。如果容器未排序，结果是未定义的。
- 如果容器中没有找到目标元素，lower_bound() 会返回指向容器末尾的迭代器，而 upper_bound() 也会返回指向容器末尾的迭代器。

总结

std::lower_bound() 和 std::upper_bound() 是非常高效的查找算法，它们通过二分查找的方式，可以快速找到已排序容器中某个元素的插入位置或其上界。lower_bound() 查找的是第一个不小于指定值的位置，而 upper_bound() 查找的是第一个大于指定值的位置。它们在查找元素、确定插入位置或查找区间时非常有用。

参考回答

详细讲解与拓展

总结

发表评论 取消回复

发表评论取消回复