← 目录 / 第十一章 · STL 标准模板库 / 11.13.2 查找与计数

11.13.2　查找与计数

find、count、max_element / min_element、binary_search、lower_bound / upper_bound —— 在数据里找东西、数东西的通用算法。

📂 引入头文件：#include <algorithm> —— 本节算法全部在这里。
本页目录
① find —— 查找元素

从前往后逐个比较，找到第一个等于目标值的元素，返回指向它的迭代器；如果找不到，返回 end()。时间复杂度 O(n)，适用于任意容器（包括无序的）。

C++ · find 查找单个元素
1vector<int> v = {3, 1, 4, 1, 5};
2auto it = find(v.begin(), v.end(), 4);
3if (it != v.end())
4{
5 cout << "找到了: " << *it << endl; // 找到了: 4
6 cout << "下标: " << (it - v.begin()) << endl; // 下标: 2
7}
8
9// 找不到时返回 end()
10auto it2 = find(v.begin(), v.end(), 99);
11if (it2 == v.end()) {
12 cout << "没找到 99" << endl;
13}
📌
判断"是否找到"的标准写法：永远是和 end() 比较（it != v.end()），不要直接判断迭代器是否为"空"——迭代器没有像指针那样天然的"空值"概念。
② count —— 统计出现次数

统计某个值在区间内出现了多少次。

C++ · count 统计次数
1vector<int> v = {1, 2, 3, 2, 2, 4};
2int cnt = count(v.begin(), v.end(), 2);
3cout << "2 出现了 " << cnt << " 次" << endl; // 2 出现了 3 次
③ max_element / min_element —— 找最大/最小值的位置

注意这两个函数返回的是迭代器（位置），不是值本身——需要解引用 *it 才能拿到具体的值。

C++ · 找最大值和最小值
1vector<int> v = {3, 1, 4, 1, 5, 9};
2
3auto max_it = max_element(v.begin(), v.end());
4cout << "最大值: " << *max_it << endl; // 最大值: 9
5cout << "下标: " << (max_it - v.begin()) << endl; // 下标: 5
6
7auto min_it = min_element(v.begin(), v.end());
8cout << "最小值: " << *min_it << endl; // 最小值: 1
📌
如果只想要值，不需要下标，可以直接写 *max_element(v.begin(), v.end())，一行解决——但每次调用都是 O(n) 重新扫描一遍，循环里频繁调用要注意效率。

只能在已排序的序列上使用，时间复杂度 O(log n)。它只告诉你"有没有"，返回一个 bool，不会告诉你具体在哪个位置——如果需要位置，要用下面的 lower_bound。

C++ · binary_search 判断元素是否存在
1vector<int> v = {1, 3, 5, 7, 9};
2
3if (binary_search(v.begin(), v.end(), 5))
4{
5 cout << "5 在数组中" << endl;
6}
7
8if (!binary_search(v.begin(), v.end(), 4))
9{
10 cout << "4 不在数组中" << endl;
11}
⑤ lower_bound / upper_bound —— 二分查找位置

同样只能在已排序的序列上使用，时间复杂度 O(log n)。和 binary_search 不同，它们返回的是位置（迭代器）：

函数含义找的是
lower_bound第一个 ≥ target 的位置下界（包含等于）
upper_bound第一个 > target 的位置上界（不包含等于）
v = {1, 2, 2, 2, 3, 4}；查找 target = 2
 
1
0
lower_bound
2
1
 
2
2
 
2
3
upper_bound
3
4
 
4
5
lower_bound 停在下标 1（第一个 ≥ 2 的位置），upper_bound 停在下标 4（第一个 > 2 的位置）。两者之间的区间 [lower_bound, upper_bound) 正好就是所有等于 2 的元素，区间长度 = 2 出现的次数。
C++ · lower_bound 与 upper_bound
1vector<int> v = {1, 2, 2, 2, 3, 4};
2
3// lower_bound：第一个 ≥ target 的位置
4auto lb = lower_bound(v.begin(), v.end(), 2);
5cout << "第一个 ≥ 2 的下标: " << (lb - v.begin()) << endl; // 输出: 1
6
7// upper_bound：第一个 > target 的位置
8auto ub = upper_bound(v.begin(), v.end(), 2);
9cout << "第一个 > 2 的下标: " << (ub - v.begin()) << endl; // 输出: 4
10
11// 等于 2 的元素个数
12cout << "2 的个数: " << (ub - lb) << endl; // 输出: 3
🎯
竞赛中 lower_bound 比 find 常用得多——对于有序数组，O(log n) 比 O(n) 快太多。map、set 这些关联容器也有自己的成员函数版本 .lower_bound()，效果一样但效率更高（不需要重新排序）。