C++ lower_bound()
C++算法lower_bound()
C++算法 lower_bound()函数是二进制搜索的版本。该函数用于返回一个迭代器，该迭代器指向不小于(即大于或等于)指定值 val 的有序范围[first，last]。
第一个版本使用运算符 来比较元素，第二个版本使用 comp 函数。
语法
default (1) template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2) template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
参数
first: 指向要搜索范围中第一个元素的前向迭代器。
last : 前向迭代器，指向要搜索范围内的最后一个元素。
comp : 用户定义的二进制谓词函数，它接受两个参数如果两个参数顺序正确，则返回true，否则返回false。遵循严格的弱排序对元素进行排序。
val : 下限的值，用于比较范围内的元素。
返回值
它返回一个迭代器，该迭代器指向范围不小于val的第一个元素，或者找不到该元素的最后一个元素。
复杂度
平均而言，复杂度在第一个和最后一个之间的距离是对数的: 最多执行log
2 (N)+ 1个元素的比较，其中N =末尾-首先。
数据竞争
访问范围为[first，last)的对象。
异常
如果元素比较或迭代器上的操作抛出异常，则此函数将引发异常。
注意: 无效参数导致未定义的行为。
示例1
让我们看一个简单的示例来演示lower_bound()的用法:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 6, 5};
decltype(v)::iterator it = lower_bound(v.begin(), v.end(), 4);
cout << *it << ", pos = " << (it-v.begin()) << endl;
return 0;
}
输出:
示例2
让我们看另一个简单的示例:
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
using namespace std;
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
vector<int>::iterator low,up;
low=lower_bound (v.begin(), v.end(), 20); // ^
up= upper_bound (v.begin(), v.end(), 20); // ^
cout << "lower_bound at position " << (low-v.begin()) << '\n';
cout << "upper_bound at position " << (up-v.begin()) << '\n';
return 0;
}
输出:
lower_bound at position 3
upper_bound at position 6
示例3
让我们看另一个简单的示例:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
template<class ForwardIt, class T, class Compare=less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
// Note: BOTH type T and the type after ForwardIt is dereferenced
// must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
// this is stricter than lower_bound requirement (see above)
first = lower_bound(first, last, value, comp);
return first != last && !comp(value, *first) ? first: last;
}
int main()
{
vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
auto lower = lower_bound(data.begin(), data.end(), 4);
auto upper = upper_bound(data.begin(), data.end(), 4);
copy(lower, upper, ostream_iterator<int>(cout, " "));
cout << '\n';
// classic binary search, returning a value only if it is present
data = { 1, 2, 4, 6, 9, 10 };
auto it = binary_find(data.cbegin(), data.cend(), 4); //< choosing '5' will return end()
if(it != data.cend())
cout << *it << " found at index "<< distance(data.cbegin(), it);
return 0;
}
输出:
示例4
让我们看另一个简单的示例:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool ignore_case(char a, char b) {
return(tolower(a) == tolower(b));
}
int main(void) {
vector<char> v = {'A', 'b', 'C', 'd', 'E'};
auto it = lower_bound(v.begin(), v.end(), 'C');
cout << "First element which is greater than \'C\' is " << *it << endl;
it = lower_bound(v.begin(), v.end(), 'C', ignore_case);
cout << "First element which is greater than \'C\' is " << *it << endl;
it = lower_bound(v.begin(), v.end(), 'z', ignore_case);
cout << "All elements are less than \'z\'." << endl;
return 0;
}
输出:
First element which is greater than 'C' is b
First element which is greater than 'C' is d
All elements are less than 'z'.
