【C++】C++11 STL算法(四)：二分查找法（Binary search operations）、合并操作

头文件：#include <algorithm>

一、lower_bound

1、原型：

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

2、说明：

返回不小于给定值的第一个元素的位置（迭代器）。

3、官方demo

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>template<class ForwardIt, class T, class Compare=std::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 = std::lower_bound(first, last, value, comp);return first != last && !comp(value, *first) ? first : last;
}int main()
{std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };auto lower = std::lower_bound(data.begin(), data.end(), 4);auto upper = std::upper_bound(data.begin(), data.end(), 4);std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));std::cout << '\n';// ：经典的二分查找，只有在存在值时才返回值data = { 1, 2, 4, 6, 9, 10 }; auto it = binary_find(data.cbegin(), data.cend(), 4); //使用 '5' 将返回 end()if(it != data.cend())std::cout << *it << " found at index "<< std::distance(data.cbegin(), it);return 0;
}

Output:

4 4 4 
4 found at index 2

二、upper_bound

1、原型：

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

2、说明：

返回大于给定值的第一个元素的位置（迭代器），如果没有返回last

3、官方demo

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>int main()
{std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };auto lower = std::lower_bound(data.begin(), data.end(), 4);auto upper = std::upper_bound(data.begin(), data.end(), 4);std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
}

Output:

4 4 4

三、binary_search

1、原型：

template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

2、说明：

确定某个元素是否存于[first, last)范围中。

3、官方demo

#include <iostream>
#include <algorithm>
#include <vector>int main()
{std::vector<int> haystack {1, 3, 4, 5, 9};std::vector<int> needles {1, 2, 3};for (auto needle : needles) {std::cout << "Searching for " << needle << '\n';if (std::binary_search(haystack.begin(), haystack.end(), needle)) {std::cout << "Found " << needle << '\n';} else {std::cout << "no dice!\n";}}
}

Output:

Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3

四、equal_range

1、原型：

template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt>equal_range( ForwardIt first, ForwardIt last, const T& value );template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt,ForwardIt>equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );

2、说明：

返回[first, last)范围内等于value的子范围

3、官方demo

#include <algorithm>
#include <vector>
#include <iostream>struct S
{int number;char name;// note: name is ignored by this comparison operatorbool operator< ( const S& s ) const { return number < s.number; }
};int main()
{// note: not ordered, only partitioned w.r.t. S defined belowstd::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };S value = {2, '?'};auto p = std::equal_range(vec.begin(), vec.end(), value);for ( auto i = p.first; i != p.second; ++i )std::cout << i->name << ' ';// heterogeneous comparison:struct Comp   {bool operator() ( const S& s, int i ) const { return s.number < i; }bool operator() ( int i, const S& s ) const { return i < s.number; }};auto p2 = std::equal_range(vec.begin(),vec.end(), 2, Comp{});for ( auto i = p2.first; i != p2.second; ++i )std::cout << i->name << ' ';
}

Output:

B C D B C D

五、merge

1、原型：

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2,OutputIt d_first );template< class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge( InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2,OutputIt d_first, Compare comp );

2、说明：

合并两个已经排序好的序列

3、官方demo

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <random>
#include <functional>int main()
{// 用随机数填充向量std::random_device rd;std::mt19937 mt(rd());std::uniform_int_distribution<> dis(0, 9);std::vector<int> v1(10), v2(10);std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));// 排序std::sort(v1.begin(), v1.end());std::sort(v2.begin(), v2.end());// output v1std::cout << "v1 : ";std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));std::cout << '\n';// output v2std::cout << "v2 : ";std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " "));std::cout << '\n';// 合并std::vector<int> dst;std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));// outputstd::cout << "dst: ";std::copy(dst.begin(), dst.end(), std::ostream_iterator<int>(std::cout, " "));std::cout << '\n';
}

Possible output:

v1 : 0 1 3 4 4 5 5 8 8 9 
v2 : 0 2 2 3 6 6 8 8 8 9 
dst: 0 0 1 2 2 3 3 4 4 5 5 6 6 8 8 8 8 8 9 9

六、inplace_merge

1、原型：

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

2、说明：

将已经排序好的两段序列[first, middle)、[middle,last)合并并且配序成[first, last)

2、官方demo

#include <vector>
#include <iostream>
#include <algorithm>template<class Iter>
void merge_sort(Iter first, Iter last)	//归并排序，参见https://www.runoob.com/w3cnote/merge-sort.html，有动图演示
{if (last - first > 1) {Iter middle = first + (last - first) / 2;merge_sort(first, middle);merge_sort(middle, last);std::inplace_merge(first, middle, last);}
}int main()
{std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};merge_sort(v.begin(), v.end());for(auto n : v) {std::cout << n << ' ';}std::cout << '\n';
}

Output:

-2 0 1 2 3 7 8 11 11