lower_bound函数解释及常用场景
lower_bound函数是C++标准库中的一个算法，主要用于在有序序列中查找第一个不小于（即大于或等于）给定值的元素。其返回的是一个迭代器，指向这个元素。如果序列中没有这样的元素，lower_bound将返回一个指向序列末尾之后的迭代器。
lower_bound函数的原型是：
```cpp
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
```
其中，first和last是指向要搜索的范围的开始和结束的迭代器，value是我们要在序列中查找的值。
lower_bound函数的返回值有两种情况：
1. 如果找到元素，返回一个指向第一个不小于value的元素的迭代器。
2. 如果没有找到这样的元素，返回一个指向last的迭代器。
lower_bound函数有多种常用场景：
1. 二分查找：lower_bound常用于实现二分查找，因为它可以在有序序列中高效地找到第一个不小于给定值的元素。
2. 插入元素到有序序列：如果你有一个有序序列，并且想要在其中插入一个新的元素，你可以使用lower_bound来找到插入位置。这样可以确保新元素插入后序列仍然有序。
3. 查找范围：与upper_bound结合使用，lower_bound可以用来查找一个值在有序序列中的范围。例如，你可以使用lower_bound找到第一个不小于给定值的元素，然后使用upper_bound找到第一个大于给定值的元素。这两个迭代器将定义一个范围，其中包含所有等于给定值的元素。
下面是一个使用lower_bound函数的示例：
```cpp
#include<iostream>
#include<vector>
#include<algorithm>
int main(){
std::vector<int> v = {1, 3, 5, 7, 9};
int value_to_find = 4;
auto it = std::lower_bound(v.begin(), v.end(), value_to_find);
if (it != v.end() && *it == value_to_find) {
std::cout << "Found " << value_to_find << " in the vector.\n";
} else {
std::cout << "Did not find " << value_to_find << " in the vector.\n";
}
return 0;
}
```
在这个示例中，我们尝试在有序向量v中查找值4。由于4小于第一个元素5，所以lower_bound函数返回了一个指向第一个元素5的迭代器。
我的内容管理
展开
