C++学习笔记（三十七）——STL之搜索算法

STL 算法分类：

类别	常见算法	作用
排序	sort、stable_sort、partial_sort、nth_element等	排序
搜索	find、find_if、count、count_if、binary_search等	查找元素
修改	copy、replace、replace_if、swap、fill等	修改容器内容
删除	remove、remove_if、unique等	删除元素
归约	for_each、accumulate等	处理数据
合并	merge、set_union、set_intersection等	处理有序序列
排列组合	next_permutation、prev_permutation等	生成排列
堆操作	push_heap、pop_heap、make_heap、sort_heap等	处理堆

STL 搜索算法

在 C++的STL 中，提供了一些用于搜索容器中元素的算法，位于 <algorithm> 头文件中。
常见的搜索算法包括 find、binary_search、find_if 等。

算法名称	功能描述	时间复杂度	空间复杂度	适用场景
find	查找容器中第一个与指定值相等的元素	O(n)	O(1)	在无序容器中查找元素
find_if	查找容器中第一个满足指定条件的元素	O(n)	O(1)	查找满足特定条件的元素
count	统计某个元素在范围内出现的次数	O(n)	O(1)	统计某个元素出现的次数
count_if	统计满足特定条件的元素数量	O(n)	O(1)	统计符合条件的元素数量
binary_search	查找容器中是否存在某个元素（要求容器已排序）	O(log n)	O(1)	在已排序的容器中查找元素
lower_bound	查找容器中第一个不小于指定值的元素	O(log n)	O(1)	在已排序的容器中查找不小于指定值的元素
upper_bound	查找容器中第一个大于指定值的元素	O(log n)	O(1)	在已排序的容器中查找大于指定值的元素
search	查找一个子序列在另一个序列中的首次出现	O(n * m)	O(1)	查找子序列在容器中的位置
search_n	查找某个值连续出现 n 次的子序列	O(n)	O(1)	查找某个值连续出现的子序列

（1） find

• 功能：在容器中查找第一个与指定值相等的元素。
• 时间复杂度：O(n)，其中 n 是容器中的元素数。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 1 };auto it = find(vec.begin(), vec.end(), 3); // 查找值为 3 的元素if (it != vec.end()){cout << "找到元素: " << *it << endl;  // 输出：找到元素: 3}else{cout << "元素未找到" << endl;}system("pause");return 0;
}

注意：

• find适用于顺序容器（如 vector、list 等）。

（2）find_if

• 功能：在容器中查找第一个满足给定条件的元素。
• 时间复杂度：O(n)，其中 n 是容器中的元素数。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>bool is_even(int n) 
{return n % 2 == 0;  // 判断是否为偶数
}int main() {vector<int> vec = { 5, 2, 8, 3, 1 };auto it = find_if(vec.begin(), vec.end(), is_even); // 查找第一个偶数if (it != vec.end()){cout << "找到偶数: " << *it << endl;  // 输出：找到偶数: 2}else{cout << "未找到偶数" << endl;}system("pause");return 0;
}

注意：

• 与 find 不同，find_if 是基于条件的查找，使用一个谓词（即一个返回布尔值的函数或仿函数）来判断元素是否满足条件。

（3） count

• 功能：计算给定范围内某个元素出现的次数。
• 时间复杂度：O(n)，其中 n 是范围中的元素数量。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 10, 20, 10, 40, 10 };// 统计 10 出现的次数int num = count(vec.begin(), vec.end(), 10);cout << "元素 10 出现了 " << num << " 次。" << endl;system("pause");return 0;
}

注意：

• count适用于，当需要统计某个元素在容器中出现的次数时使用。

（4） count_if

• 功能：计算给定范围内满足特定条件的元素的数量。
• 时间复杂度：O(n)，其中 n 是范围中的元素数量。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>bool is_even(int n)
{return n % 2 == 0;
}int main() {vector<int> vec = { 1, 2, 3, 4, 5, 6 };// 统计偶数元素的数量int num = count_if(vec.begin(), vec.end(), is_even);cout << "有 " << num << " 个偶数元素。" << endl;system("pause");return 0;
}

注意：

• count_if适用于，当需要统计满足某个条件的元素数量时使用。

（5） binary_search

• 功能：判断容器中是否存在某个元素，要求容器必须已经是有序的。
• 时间复杂度：O(log n)，n 是容器中的元素数。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 5, 8 };  // 已经排序bool found = binary_search(vec.begin(), vec.end(), 3); // 查找是否有 3cout << (found ? "找到" : "未找到") << endl;  // 输出：找到found = binary_search(vec.begin(), vec.end(), 4); // 查找是否有 4cout << (found ? "找到" : "未找到") << endl;  // 输出：未找到system("pause");return 0;
}

注意：

• binary_search适用于有序容器。它返回布尔值，表示是否找到目标元素。

（6）lower_bound

• 功能：返回指向容器中第一个不小于指定值的元素的迭代器。
• 时间复杂度：O(log n)，n 是容器中的元素数。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 5, 8 };  // 已经排序auto it = lower_bound(vec.begin(), vec.end(), 3); // 查找大于等于 3 的第一个元素if (it != vec.end()) {cout << "找到元素: " << *it << endl;  // 输出：找到元素: 3}else{cout << "未找到元素" << endl;}system("pause");return 0;
}

注意：

• lower_bound适用于有序容器。它可以用来查找某个值或第一个大于等于该值的元素。

（7）upper_bound

• 功能：返回指向容器中第一个大于指定值的元素的迭代器。
• 时间复杂度：O(log n)，n 是容器中的元素数。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 5, 8 };  // 已经排序auto it = upper_bound(vec.begin(), vec.end(), 3); // 查找大于 3 的第一个元素if (it != vec.end()){cout << "找到元素: " << *it <<endl;  // 输出：找到元素: 5}else{cout << "未找到元素" << endl;}system("pause");return 0;
}

注意：

• upper_bound适用于有序容器。它返回一个迭代器，指向第一个比指定值大的元素。

（8） search

• 功能：在一个范围中查找另一个范围（子序列）的第一次出现。
• 时间复杂度：O(n * m)，其中 n 是第一个范围的大小，m 是第二个范围的大小。
• 空间复杂度：O(1)。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 4, 5, 6 };vector<int> subvec = { 3, 4 };// 查找子序列 subvec 在 vec 中的首次出现auto it = std::search(vec.begin(), vec.end(), subvec.begin(), subvec.end());if (it != vec.end()){cout << "子序列 subvec 在 vec 中的首次出现的位置: " << distance(vec.begin(), it) << endl;}else{cout << "未找到子序列subvec" << endl;}system("pause");return 0;
}

注意：

• search适用于查找一个子序列在另一个序列中的位置。

（9） search_n

• 功能：在给定范围内查找一个值连续出现的子序列（即连续 n 次相同的元素）。
• 时间复杂度：O(n)，其中 n 是范围中的元素数量。
• 空间复杂度：O(1)。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 2, 2, 3, 4 };// 查找连续出现 3 次的元素 2auto it = search_n(vec.begin(), vec.end(), 3, 2);if (it != vec.end()){cout << "连续出现 3 次的元素 2 的首次出现的位置: " << distance(vec.begin(), it) << endl;}else{cout << "未找到连续出现 3 次的元素 2" << endl;}system("pause");return 0;
}

注意：

• search_n适用于查找某个值连续出现的子序列。