C++算法 lower_bound()函数是二进制搜索的版本。该函数用于返回一个迭代器,该迭代器指向不小于(即大于或等于)指定值 val 的有序参数[first,last]。
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的参数中的第一个元素;如果找不到该元素,则返回last。
让我们看一个简单的例子来演示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; }
输出:
4, pos = 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
让我们看另一个简单的例子:
#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 4 4 4 found at index 2
让我们看另一个简单的例子:
#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'.
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)
Spring Cloud 微服务项目实战 -〔姚秋辰(姚半仙)〕