当处理有序序列时,C++的STL库提供了lower_bound
和upper_bound
两个函数,它们用于在有序序列中进行二分查找,从而找到特定值的插入位置或者特定范围的元素。
lower_bound
函数的定义如下:
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
-
lower_bound
:
lower_bound
函数返回一个迭代器,指向序列中第一个不小于给定值的元素。
如果给定值存在于序列中,则返回指向该值的迭代器;否则,返回指向第一个大于给定值的元素的迭代器。 -
upper_bound
:
upper_bound
函数返回一个迭代器,指向序列中第一个大于给定值的元素。
即使给定值存在于序列中,upper_bound
也会返回指向第一个大于给定值的元素的迭代器。
下面是一个简单的示例来展示它们的用法:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {10, 20, 30, 30, 30, 40, 50};
// lower_bound示例
auto lb = lower_bound(vec.begin(), vec.end(), 30);
if (lb != vec.end()) {
cout << "Lower bound of 30 at position: " << distance(vec.begin(), lb) << endl;
}
// upper_bound示例
auto ub = upper_bound(vec.begin(), vec.end(), 30);
if (ub != vec.end()) {
cout << "Upper bound of 30 at position: " << distance(vec.begin(), ub) << endl;
}
return 0;
}
在这个示例中,lower_bound
函数找到了第一个不小于30的元素(即30所在的位置),而upper_bound
找到了第一个大于30的元素的位置。
善