参考：执行策略：cppreference.com

---

一、find系列函数（单个元素顺序查找）

该算法提供范围内查找对象的算法，在<algorithm>头文件中定义。

指向首个满足条件的迭代器，或若找不到这种元素则为 last 。

参考自：《https://zh.cppreference.com/w/cpp/algorithm/find》

1. find 搜索等于 value 的元素。

// 在范围 [first, last) 中满足特定判别标准的首个元素
template< class InputIt, class T >
constexpr InputIt find( InputIt first, InputIt last, const T& value );

template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, const T& value );

2. find_if 搜索谓词 p 对其返回 true 的元素

参数说明：p - 若为要求的元素则返回 ​true 的一元谓词。

template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if( InputIt first, InputIt last,
                           UnaryPredicate p );

// 指定执行策略
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                 UnaryPredicate p );

3. find_if_not 搜索谓词 q 对其返回 false 的元素。

参数说明：q - 若为要求的元素则返回 ​false 的一元谓词。

template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if_not( InputIt first, InputIt last,
                               UnaryPredicate q );

// 指定执行策略
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if_not( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                     UnaryPredicate q );

测试用例

int main()
{
	vector<int>vec{ 3,6,10,8,7,9,1,5,2,4 };		// vector_int
	int val = 7;

test1:// find 

	auto ret1 = find(vec.begin(), vec.end(), val);	// 查找
	if (ret1 != vec.end())	// 如果找到，输出
	{
		cout << " vec[" << distance(vec.begin(), ret1) << "] == " << val << endl;
	}
	// 输出:  vec[4] == 7

test2:// find_if

	auto ret2 = find_if(vec.begin(), vec.end(),
		[val](int v) {return v == val; });	// 查找 等于val的元素

	if (ret2 != vec.end())
	{
		cout << " vec[" << distance(vec.begin(), ret2) << "] == " << val << endl;
	}
	// 输出:  vec[4] == 7

test3:// find_if_not  

	auto ret3 = find_if_not(vec.begin(), vec.end(), 
		[val](int v) {return v != val; });	// 查找，不满足 (v != val) 的数
											// 　　　即，v==val

	if (ret3 != vec.end())
	{
		cout << " vec[" << distance(vec.begin(), ret3) << "] == " << val << endl;
	}
	// 输出:  vec[4] == 7

	return 0;
}

一、二分查找系列函数（单个元素二分查找）

注：二分查找的基础是给定范围是有序排列的。

1. lower_bound 二分查找大于等于

返回指向范围 [first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素则返回 last 。

// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

2. upper_bound 二分查找大于

返回指向范围 [first, last) 中首个大于 value 的元素的迭代器，或若找不到这种元素则返回 last 。采用二分实现，所以调用前必须保证有序。

// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

3. equal_range 二分查找等价区间

返回范围 [first, last) 中含有所有等价于 value 的元素的范围。

含有定义所需范围的一对迭代器的 std::pair ，第一迭代器指向首个不小于 value 的元素，而第二迭代器指向首个大于 value 的元素。

若无元素小于 value ，则 last 作为第一元素返回。类似地，若无元素大于 value ，则 last 作为第二元素返回。

// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt,ForwardIt>
              equal_range( ForwardIt first, ForwardIt last,
                           const T& value );

// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt,ForwardIt>
              equal_range( ForwardIt first, ForwardIt last,
                           const T& value, Compare comp );

4. binary_search 二分查找是否存在元素value

检查等价于 value 的元素是否出现于范围 [first, last) 中。

若找到等于 value 的元素则为 true ，否则为 false 。

// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );

// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

测试用例

int main()
{
	vector<int>vec{ 3,6,10,8,7,9,1,5,2,4 };		// vector_int
	sort(vec.begin(), vec.end(), less<int>());	// 排序 ｛1,...10｝
	int val = 7;

test1:// lower_bound 大于等于

	auto ret1 = lower_bound(vec.begin(), vec.end(), val);	// 查找，大于等于
	if (ret1 != vec.end())	// 如果找到，输出
	{
		cout << "( vec[" << distance(vec.begin(), ret1) << "] == " << *ret1
			<< " ) >= " << val << endl;
	}
	// 输出: ( vec[6] == 7 ) >= 7 

test2:// upper_bound 大于

	auto ret2 = upper_bound(vec.begin(), vec.end(), val);	// 查找，大于
	if (ret2 != vec.end())	
	{
		cout << "( vec[" << distance(vec.begin(), ret2) << "] == " << *ret2
			<< " ) > " << val << endl;
	}
	// 输出: ( vec[7] == 8 ) > 7

test3:// equal_range 

	vector<int> vecs{ 1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7 };
	int vals = 4;
	auto ret3 = equal_range(vecs.begin(), vecs.end(), vals);	// 查找，等价区间

	for(auto i = ret3.first; i != ret3.second; i++)
	{
		cout << " vec[" << distance(vec.begin(), ret2) << "] == " << *i << "\n";
	}
	/* 输出: 
		 vec[7] == 4
		 vec[7] == 4
		 vec[7] == 4
	 */

	return 0;
}

三、子序列查找 search

搜索范围 [first, last - (s_last - s_first)) 中元素子序列 [s_first, s_last) 的首次出现。

指向范围中 [first, last - (s_last - s_first)) ，首个子序列 [s_first, s_last) 起始的迭代器。若找不到这种子序列，则返回 last

参考自《https://zh.cppreference.com/w/cpp/algorithm/search》

1. 使用operator== 比较

// 元素用 operator== 比较
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                             ForwardIt2 s_first, ForwardIt2 s_last );

// 指定执行策略
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

2. 用给定的二元谓词 p 比较

// 元素用给定的二元谓词 p 比较
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                             ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

// 指定执行策略
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

3. 在序列 [first, last) 中搜索 searcher 构造函数中指定的模式

注： 此函数返回searcher.operator() 的结果，即指向找到的子串位置的迭代器，或若找不到则为 last

// 在序列 [first, last) 中搜索 searcher 构造函数中指定的模式。等效地执行 
//								return searcher(first, last).first;
template<class ForwardIt, class Searcher>
constexpr ForwardIt search( ForwardIt first, ForwardIt last,
                            const Searcher& searcher );

测试用例

int main()
{
	string str = { "It was Christmas Eve, a cold dark evening."
				"There was coming a little poor girl."
				"She was so cold and hungry."
				"But she had to stay on the street."
				"She had to sell the matches." }; 		// string 

	// search 

	string sub = "a little poor girl";
	auto res = search(str.begin(), str.end(), sub.begin(),sub.end());	// 查找 

	if (res != str.end())	// 输出该句及其之后的内容
	{
		int start = distance(str.begin(), res);
		int end = distance(res, str.end());
		cout << str.substr(start, end) << endl;
	}

	return 0;
}