查找与计数算法：find, find_if, search, binary_search, lower_bound, upper_bound, equal_range
说实话，STL 里的查找算法，是我日常开发中用得最频繁的工具之一。不管是写业务逻辑还是做底层优化，总免不了要在容器里翻翻找找。今天咱们就把这些算法掰开揉碎了聊一聊。
线性查找：find 与 find_if
find 是最朴素的查找方式。它从容器头走到尾，找到第一个匹配的值就返回迭代器。找不到？返回 end()。
std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
auto it = std::find(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
// 找到了，it 指向 5
}我个人习惯用 find 来查简单类型。但如果你要按条件查，就得用 find_if 了。
// 查找第一个大于 5 的元素
auto it = std::find_if(vec.begin(), vec.end(),
[](int x) { return x > 5; });小技巧：find_if 的 lambda 里可以捕获外部变量，灵活度很高。我在项目中经常用它来查「符合某个状态的对象」。
子序列查找：search
search 是用来查子序列的。比如你在一个长数组里找「1, 2, 3」这个模式第一次出现的位置。
std::vector<int> big = {0, 1, 2, 3, 4, 1, 2, 3, 5};
std::vector<int> pattern = {1, 2, 3};
auto it = std::search(big.begin(), big.end(),
pattern.begin(), pattern.end());
// it 指向 big 中第一个 1嗯，这里要注意：search 用的是朴素匹配，不是 KMP。数据量大的时候性能会差一些。我曾经在一个日志分析工具里用 search 查模式，结果几百万条记录跑了半天。后来换了手写的 KMP，速度提升了十几倍。
避坑指南：search 在 C++17 之后有 search 的并行版本，但默认还是串行的。如果你在超大容器上频繁调用，建议评估一下性能。
二分查找：binary_search
二分查找的前提是——数据必须有序。这个前提很多人会忽略。
std::vector<int> sorted = {1, 2, 3, 5, 8, 13, 21};
bool found = std::binary_search(sorted.begin(), sorted.end(), 8);
// found == true为什么强调有序？因为 binary_search 内部用的是二分法，每次砍掉一半。如果数据无序，结果就是未定义的。我曾经接手过一个项目，前任工程师在无序的 vector 上用了 binary_search，查了半天查不到数据，最后发现是排序没做。
核心要点：binary_search 只返回 true/false，不告诉你位置。想知道位置？用 lower_bound 或 upper_bound。
边界查找：lower_bound 与 upper_bound
这两个函数是二分查找的「进阶版」。它们返回的是迭代器，指向某个边界位置。
lower_bound：返回第一个 不小于 目标值的位置upper_bound：返回第一个 大于 目标值的位置
std::vector<int> v = {1, 2, 2, 2, 3, 4, 5};
auto low = std::lower_bound(v.begin(), v.end(), 2);
auto up = std::upper_bound(v.begin(), v.end(), 2);
// low 指向第一个 2（索引 1）
// up 指向 3（索引 4）你想想看，这两个组合起来，就能拿到所有等于目标值的元素范围。这就是 equal_range 干的事。
范围查找：equal_range
equal_range 返回一个 pair，里面装着 lower_bound 和 upper_bound 的结果。
auto range = std::equal_range(v.begin(), v.end(), 2);
// range.first == lower_bound
// range.second == upper_bound
// 区间 [range.first, range.second) 里全是 2我个人觉得 equal_range 在统计重复元素时特别好用。比如你要统计某个分数段的人数，用 equal_range 一次搞定。
经验之谈：如果你只需要判断是否存在，用 binary_search。如果你需要插入位置（比如维护有序容器），用 lower_bound。如果你需要统计重复个数，用 equal_range。
知识体系总览
下面这张图把今天讲的算法按「是否有序」和「查找目标」做了分类。建议你保存下来，写代码时对照着看。
性能对比一览
| 算法 | 时间复杂度 | 前提条件 | 返回值 |
|---|---|---|---|
| find | O(n) | 无 | 迭代器 |
| find_if | O(n) | 无 | 迭代器 |
| search | O(n*m) | 无 | 迭代器 |
| binary_search | O(log n) | 有序 | bool |
| lower_bound | O(log n) | 有序 | 迭代器 |
| upper_bound | O(log n) | 有序 | 迭代器 |
| equal_range | O(log n) | 有序 | pair<迭代器, 迭代器> |
重要提醒：binary_search 系列算法要求随机访问迭代器。对 list 或 forward_list 用二分查找？编译器不会报错，但性能会退化到 O(n log n)，而且结果可能不对。我见过有人把 list 传给 lower_bound，查了半天位置是错的，就是因为迭代器类型不匹配。
好了，今天的内容就到这里。这些算法看着简单，但用对地方能省不少事。下次写代码时，先想想你的数据是有序还是无序，再选合适的算法。别一上来就 find 走天下。