find、count、max_element / min_element、binary_search、lower_bound / upper_bound —— 在数据里找东西、数东西的通用算法。
从前往后逐个比较，找到第一个等于目标值的元素，返回指向它的迭代器；如果找不到，返回 end()。时间复杂度 O(n)，适用于任意容器（包括无序的）。
| 1 | vector<int> v = {3, 1, 4, 1, 5}; |
| 2 | auto it = find(v.begin(), v.end(), 4); |
| 3 | if (it != v.end()) |
| 4 | { |
| 5 | cout << "找到了: " << *it << endl; // 找到了: 4 |
| 6 | cout << "下标: " << (it - v.begin()) << endl; // 下标: 2 |
| 7 | } |
| 8 | |
| 9 | // 找不到时返回 end() |
| 10 | auto it2 = find(v.begin(), v.end(), 99); |
| 11 | if (it2 == v.end()) { |
| 12 | cout << "没找到 99" << endl; |
| 13 | } |
end() 比较（it != v.end()），不要直接判断迭代器是否为"空"——迭代器没有像指针那样天然的"空值"概念。统计某个值在区间内出现了多少次。
| 1 | vector<int> v = {1, 2, 3, 2, 2, 4}; |
| 2 | int cnt = count(v.begin(), v.end(), 2); |
| 3 | cout << "2 出现了 " << cnt << " 次" << endl; // 2 出现了 3 次 |
find、count 是通用算法，对任何容器都适用，但代价是只能"逐个遍历比较"，时间复杂度 O(n)。set、map 这类关联容器内部是有序结构（红黑树），自带了效率更高的成员函数 .find()、.count()，时间复杂度是 O(log n)。也就是说，find(s.begin(), s.end(), x) 和 s.find(x) 效果一样，但后者快得多——用 set/map 时，永远优先用它们自己的成员函数，而不是这里的通用算法。注意这两个函数返回的是迭代器（位置），不是值本身——需要解引用 *it 才能拿到具体的值。
| 1 | vector<int> v = {3, 1, 4, 1, 5, 9}; |
| 2 | |
| 3 | auto max_it = max_element(v.begin(), v.end()); |
| 4 | cout << "最大值: " << *max_it << endl; // 最大值: 9 |
| 5 | cout << "下标: " << (max_it - v.begin()) << endl; // 下标: 5 |
| 6 | |
| 7 | auto min_it = min_element(v.begin(), v.end()); |
| 8 | cout << "最小值: " << *min_it << endl; // 最小值: 1 |
*max_element(v.begin(), v.end())，一行解决——但每次调用都是 O(n) 重新扫描一遍，循环里频繁调用要注意效率。与前面的 find（O(n)，逐个遍历比较）不同，binary_search 系列算法要求数据已经排好序，但作为交换条件，能以 O(log n) 的速度完成查找——数据量大的时候，这个速度差距会非常明显（比如 n=100万 时，O(n) 要比较约 100 万次，O(log n) 只需要约 20 次）。它只告诉你"有没有"，返回一个 bool，不会告诉你具体在哪个位置——如果需要位置，要用下面的 lower_bound。
| 1 | vector<int> v = {1, 3, 5, 7, 9}; |
| 2 | |
| 3 | if (binary_search(v.begin(), v.end(), 5)) |
| 4 | { |
| 5 | cout << "5 在数组中" << endl; |
| 6 | } |
| 7 | |
| 8 | if (!binary_search(v.begin(), v.end(), 4)) |
| 9 | { |
| 10 | cout << "4 不在数组中" << endl; |
| 11 | } |
同样只能在已排序的序列上使用，时间复杂度 O(log n)。和 binary_search 不同，它们返回的是位置（迭代器）：
| 函数 | 含义 | 找的是 |
|---|---|---|
| lower_bound | 第一个 ≥ target 的位置 | 下界（包含等于） |
| upper_bound | 第一个 > target 的位置 | 上界（不包含等于） |
lower_bound 停在下标 1（第一个 ≥ 2 的位置），upper_bound 停在下标 4（第一个 > 2 的位置）。两者之间的区间 [lower_bound, upper_bound) 正好就是所有等于 2 的元素，区间长度 = 2 出现的次数。| 1 | vector<int> v = {1, 2, 2, 2, 3, 4}; |
| 2 | |
| 3 | // lower_bound：第一个 ≥ target 的位置 |
| 4 | auto lb = lower_bound(v.begin(), v.end(), 2); |
| 5 | cout << "第一个 ≥ 2 的下标: " << (lb - v.begin()) << endl; // 输出: 1 |
| 6 | |
| 7 | // upper_bound：第一个 > target 的位置 |
| 8 | auto ub = upper_bound(v.begin(), v.end(), 2); |
| 9 | cout << "第一个 > 2 的下标: " << (ub - v.begin()) << endl; // 输出: 4 |
| 10 | |
| 11 | // 等于 2 的元素个数 |
| 12 | cout << "2 的个数: " << (ub - lb) << endl; // 输出: 3 |
lower_bound 比 find 常用得多——对于有序数组，O(log n) 比 O(n) 快太多。map、set 这些关联容器也有自己的成员函数版本 .lower_bound()，效果一样但效率更高（不需要重新排序）。target 比序列里所有元素都大，lower_bound（以及 upper_bound）会返回 end()——这代表"没有任何元素满足条件"。end() 并不指向一个真实存在的元素，在计算下标或者用 *it 解引用之前，一定要先判断 it != v.end()，否则解引用 end() 是未定义行为，很容易导致程序崩溃或者读到一堆垃圾值。