39、STL算法（排序与查找）：sort、find、binary_search、lower_bound
排序和查找，说白了就是C++里最常用的两个操作。我做了这么多年项目，几乎每个工程都离不开它们。今天咱们就聊聊STL里这几个核心算法——sort、find、binary_search、lower_bound。
你想想看，如果让你自己手写一个快速排序或者二分查找，是不是挺麻烦的？STL把这些都封装好了，直接用就行。但问题来了——很多人用错了，或者用得不合适。嗯，这里要注意，选对算法比写对代码更重要。
排序：sort 和 stable_sort
sort 是我用得最多的算法之一。它底层用的是快速排序的改进版——内省排序（IntroSort）。说白了就是：数据量小的时候用插入排序，数据量大且递归深度浅的时候用快速排序，递归太深了就换堆排序。这样既快又稳。
核心要点：sort 默认按升序排列，时间复杂度 O(N log N)。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9, 3};
// 默认升序
std::sort(vec.begin(), vec.end());
// 降序：用 lambda 或 greater<>()
std::sort(vec.begin(), vec.end(), std::greater<int>());
// 自定义排序：按绝对值
std::sort(vec.begin(), vec.end(),
[](int a, int b) { return std::abs(a) < std::abs(b); });
for (int v : vec) std::cout << v << " ";
return 0;
}我在项目中遇到过一个问题：需要对一个结构体数组按多个字段排序。比如先按年龄排，年龄相同再按姓名排。这时候用 lambda 就特别方便：
struct Person {
std::string name;
int age;
};
std::vector<Person> people = {...};
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
if (a.age != b.age) return a.age < b.age;
return a.name < b.name;
});我的习惯：如果排序后不需要保持相等元素的原始顺序，用 sort 就够了。如果需要保持稳定排序（比如先按时间排，再按优先级排），那就用 stable_sort。不过 stable_sort 会慢一些，因为它底层是归并排序。
查找：find 和 find_if
find 是最朴素的线性查找。它从容器头走到尾，找到第一个匹配的元素就返回迭代器。时间复杂度 O(N)。
std::vector<int> vec = {10, 20, 30, 40, 50};
auto it = std::find(vec.begin(), vec.end(), 30);
if (it != vec.end()) {
std::cout << "找到了: " << *it << std::endl;
} else {
std::cout << "没找到" << std::endl;
}那 find_if 呢？它允许你传一个条件。比如我想找第一个大于25的元素：
auto it = std::find_if(vec.begin(), vec.end(),
[](int x) { return x > 25; });我曾经踩过的坑：find 返回的是迭代器，不是 bool。很多人刚学的时候会写成 if (std::find(...))，这不对。一定要判断返回值是否等于 end()。另外，find 只适用于无序数据。如果你已经排好序了，就别用 find 了——用 binary_search 或者 lower_bound 更快。
二分查找：binary_search 和 lower_bound
这两个算法要求数据必须是已排序的。时间复杂度 O(log N)，比线性查找快得多。
binary_search 只告诉你「有没有」，返回 bool。而 lower_bound 返回第一个不小于目标值的位置（迭代器）。
std::vector<int> sorted = {1, 3, 5, 7, 9, 11, 13};
// binary_search：判断是否存在
bool found = std::binary_search(sorted.begin(), sorted.end(), 7);
std::cout << (found ? "存在" : "不存在") << std::endl;
// lower_bound：找到第一个 >= 7 的位置
auto it = std::lower_bound(sorted.begin(), sorted.end(), 7);
if (it != sorted.end()) {
std::cout << "第一个 >= 7 的元素是: " << *it << std::endl;
std::cout << "下标是: " << (it - sorted.begin()) << std::endl;
}你可能会问：那 upper_bound 呢？它返回第一个大于目标值的位置。配合 lower_bound 可以找到某个值的区间范围。
实用技巧：lower_bound 和 upper_bound 配合使用，可以快速统计某个值出现的次数：auto range = std::equal_range(vec.begin(), vec.end(), value); 返回一对迭代器，就是所有等于 value 的元素范围。
知识体系总览
下面这张图帮你理清这几个算法的关系和使用场景：
实战对比：什么时候用哪个？
| 场景 | 推荐算法 | 时间复杂度 | 前提条件 |
|---|---|---|---|
| 数据量小，无序 | find | O(N) | 无 |
| 数据量大，无序 | 先 sort 再 binary_search | O(N log N) + O(log N) | 排序后 |
| 数据量大，已排序 | binary_search / lower_bound | O(log N) | 已排序 |
| 需要插入位置 | lower_bound / upper_bound | O(log N) | 已排序 |
| 查找所有匹配值 | equal_range | O(log N) | 已排序 |
我个人习惯：如果数据量小于100，用 find 就够了，没必要排序。如果数据量上千上万，而且查找操作很频繁，那就先排好序，后面都用二分查找。这叫「一次排序，多次受益」。
避坑指南
我曾经犯过一个低级错误：对一个未排序的 vector 用了 binary_search，结果有时候能找到，有时候找不到。调试了半天才发现问题——binary_search 的前提是数据必须有序。这个坑很多人都会踩。
还有一次，我用 lower_bound 找插入位置，然后直接 insert。结果忘了 lower_bound 返回的是迭代器，而 vector 的 insert 在中间位置是 O(N) 的。如果插入操作很多，性能会急剧下降。这时候应该考虑用 set 或 map。
重要提醒：lower_bound 和 upper_bound 要求数据是「按升序排列」的。如果你用了降序排列，那就得传自定义比较器，否则结果会错。我建议统一用升序，省心。
好了，这几个算法其实不难，关键是理解它们的适用场景。排序用 sort，无序查找用 find，有序查找用 binary_search 和 lower_bound。记住这个口诀，基本不会用错。