lower_bound( )
时间: 2023-12-03 20:41:05 浏览: 36
lower_bound()是C++ STL标准库中的一个查找函数,它的作用是在一个有序的序列中查找第一个大于或等于给定值的元素,并返回该元素的迭代器。如果序列中不存在大于或等于给定值的元素,则返回序列的end()迭代器。lower_bound()函数的底层实现采用的是二分查找的方式,因此它的时间复杂度为O(logn)。
下面是lower_bound()函数的两种语法格式:
```c++
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
```
其中,first和last分别表示序列的起始位置和终止位置,val表示要查找的值,comp表示比较函数。
下面是一个使用lower_bound()函数的例子,假设我们有一个有序的数组arr,我们要查找第一个大于或等于给定值x的元素:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(int);
int x = 6;
int* pos = lower_bound(arr, arr + n, x);
if (pos == arr + n) {
cout << "not found" << endl;
} else {
cout << *pos << endl;
}
return 0;
}
```
输出结果为7,因为7是数组中第一个大于或等于6的元素。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)