upper_bound函数和lower_bound函数有什么区别?
时间: 2024-06-16 20:08:09 浏览: 11
upper_bound和lower_bound都是STL中的函数,它们都用于在一个已排序的序列中寻找给定值的位置。
区别在于:
lower_bound函数返回序列中第一个不小于给定值的位置,如果序列中所有的元素都小于给定值,则返回序列末尾的位置。
而upper_bound函数返回序列中第一个大于给定值的位置,如果序列中所有的元素都小于或等于给定值,则返回序列末尾的位置。
这两个函数都可以用二分查找来实现,时间复杂度为O(logn)。
相关问题
如何实现lower_bound和upper_bound函数?
lower_bound和upper_bound是C++标准库中的两个函数,用于在有容器(如数组、向量、集合等)中查找特定值的位置1. lower_bound函数:
lower_bound函数用于查找第一个大于或等于给定值的元素的位置。它的实现方式如下:
- 首先,确定查找范围的起始位置和结束位置,通常是容器的begin()和end()迭代器。
- 然后,使用二分查找算法,在查找范围内不断缩小查找区间,直到找到第一个大于或等于给定值的元素。
- 最后,返回该元素的位置。
2. upper_bound函数:
upper_bound函数用于查找第一个大于给定值的元素的位置。它的实现方式与lower_bound函数类似,只是在找到第一个大于给定值的元素后停止查找。
下面是一个示例代码,演示了如何实现lower_bound和upper_bound函数:
```cpp
template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
while (first != last) {
ForwardIterator mid = first + std::distance(first, last) / 2;
if (*mid < value) {
first = mid + 1;
} else {
last = mid;
}
}
return first;
}
template <typename ForwardIterator, typename T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value) {
while (first != last) {
ForwardIterator mid = first + std::distance(first, last) / 2;
if (value < *mid) {
last = mid;
} else {
first = mid + 1;
}
}
return first;
}
```
STL lower_bound 函数与 upper_bound 函数,
STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的数据结构和算法。其中,lower_bound函数和upper_bound函数是STL中的两个查找函数。
lower_bound函数用于在有序序列中查找第一个大于或等于给定值的元素的位置,返回一个迭代器指向该位置。如果序列中不存在大于或等于给定值的元素,则返回指向序列末尾的迭代器。
upper_bound函数用于在有序序列中查找第一个大于给定值的元素的位置,返回一个迭代器指向该位置。如果序列中不存在大于给定值的元素,则返回指向序列末尾的迭代器。
这两个函数都需要在使用之前确保序列已经按照升序排列。它们的使用方式如下:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 4, 5, 6};
// 使用lower_bound函数查找第一个大于等于3的元素
auto lower = std::lower_bound(nums.begin(), nums.end(), 3);
if (lower != nums.end()) {
std::cout << "lower_bound: " << *lower << std::endl;
}
// 使用upper_bound函数查找第一个大于4的元素
auto upper = std::upper_bound(nums.begin(), nums.end(), 4);
if (upper != nums.end()) {
std::cout << "upper_bound: " << *upper << std::endl;
}
return 0;
}
```
输出结果为:
```
lower_bound: 3
upper_bound: 5
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)