第 6 章：基础排序与查找 (Sorting & Searching)

6.1 排序：不止是大到小

我们在第 3 章学过 std::sort。在实战中，我们几乎从不手写快速排序（Quick Sort）或归并排序（Merge Sort），除非题目强制要求求“逆序对”。

竞赛中的重点是：结构体排序。

6.1.1 自定义比较器 (Comparator)

场景：有 $N$ 个学生，每个学生有分数和学号。要求按分数从高到低排序；如果分数相同，按学号从小到大排序。

这是一个典型的多关键字排序。我们需要写一个 cmp 函数告诉 sort 谁应该排在前面。

struct Student {
    int id;
    int score;
};
 
// 比较函数：如果 a 应该排在 b 前面，返回 true
bool cmp(Student a, Student b) {
    if (a.score != b.score) {
        return a.score > b.score; // 分数高的在前
    }
    return a.id < b.id; // 分数相同时，学号小的在前
}
 
// 在 main 中：
// vector<Student> students; ...
sort(students.begin(), students.end(), cmp);

💡 现代 C++ 写法：你也可以使用 Lambda 表达式直接把函数写在 sort 里，看起来更酷： sort(v.begin(), v.end(), [](Student a, Student b) { ... });

6.2 二分查找：魔法般的折半

二分查找 (Binary Search) 的核心思想是：每次查找都将搜索范围减半。这使得查找次数从 $N$ 降到了 $\log_2 N$ 。在 $N=10^{18}$ 的天文数字下，二分也只需要找 60 次左右！

6.2.1 基础二分：在有序数组中找数

这是基本功，STL 的 lower_bound 已经帮我们做好了（见第 3 章）。但在很多复杂逻辑中，我们需要手写二分。

6.2.2 进阶核心：二分答案 (Binary Search on Answer)

这是本章的重中之重。很多算法题看起来不是查找题，但实际上是在“猜”答案。

适用特征：

答案具有单调性（Monotonicity）。
- 比如：如果“速度”为 $X$ 时能完成任务，那么速度 $>X$ 时一定也能完成；速度 $<X$ 时不一定。
- 题目通常问：“最大化最小值”或“最小化最大值”。

通用解题模板：我们不再枚举答案，而是二分答案。假设答案是 mid，我们写一个 check(mid) 函数来判断这个答案是否合法。

// 查找满足 check(mid) == true 的最小/最大值
// 区间 [L, R] 包含了可能的答案范围
long long l = 0, r = 1e9, ans = -1;
 
while (l <= r) {
    long long mid = l + (r - l) / 2; // 防止 (l+r) 溢出
    if (check(mid)) {
        ans = mid;     // 记录当前可行解
        // 如果要找更小的合法值，就往左找：r = mid - 1
        // 如果要找更大的合法值，就往右找：l = mid + 1
        l = mid + 1;   // 例如：寻找最大值
    } else {
        r = mid - 1;   // mid 不行，说明太大了（假设单调递增）
    }
}
cout << ans << endl;

案例：伐木工 (P2440)

题目：有 $N$ 根木头，长度不一。要把它们切割成 $K$ 段等长的小段，求这一小段的最大长度。
思路：
- 如果长度为 10cm 能切出来，那 9cm 肯定也能（单调性）。
- 我们二分长度 mid。
- check(mid)：遍历所有木头，算算能切出多少段。如果总段数 $\ge K$ ，说明 mid 可行（记录答案，并尝试更大的）；否则说明 mid 太长了。

6.3 双指针 (Two Pointers)：巧妙的 $O(N)$

有些问题需要在序列里找到两个元素，或者一段区间。暴力法往往是两层循环 $O(N^2)$ ，而双指针可以优化到 $O(N)$ 。

6.3.1 对撞指针

场景：在一个有序数组中，找到两个数，使它们的和等于 $Target$ 。

指针：L 指向开头，R 指向结尾。
逻辑：
- 若 arr[L] + arr[R] > Target：和太大了，R 必须左移（变小）。
- 若 arr[L] + arr[R] < Target：和太小了，L 必须右移（变大）。
- 直到 L == R 结束。
效率：每个元素最多被访问一次， $O(N)$ 。

6.3.2 尺取法 (Sliding Window / Caterpillar Method)

场景：找到一个连续子数组，使其和 $\ge S$ ，且长度最小。

形象理解：像一条毛毛虫在数组上爬。
逻辑：
1. 伸头：右指针 R 向右移，累加数值。
2. 收尾：当总和 $\ge S$ 时，满足条件了。尝试让左指针 L 向右移（缩短身体），看看能不能保持 $\ge S$ 且长度更短。

6.4 离散化 (Discretization) —— 选修技巧

有时候，数组里的值非常大（比如 $10^9$ ），但我们只关心它们的相对大小关系，且数字的总个数 $N$ 只有 $10^5$ 。为了用这些值作为数组下标（开不了 $10^9$ 的数组），我们将它们映射为 $1, 2, 3, \dots, N$ 。

实现三步走：

把所有数放进 vector。
排序 + 去重。
用 lower_bound 查找原数在去重后数组中的下标（Rank）。

vector<int> a = {100000, 20, 9999999, 20}; // 原数据
vector<int> b = a; // 备份
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 去重
 
// 查询 9999999 对应的排名（离散化后的值）
int rank = lower_bound(b.begin(), b.end(), 9999999) - b.begin() + 1;
// rank 将会是 3（因为从小到大它是第3种数）

🧠 本章小结与练习

排序解决了数据的无序性，二分解决了查找的效率，双指针解决了区间遍历的冗余。这三者是 $O(N \log N)$ 和 $O(N)$ 时代的基石。

练习作业：

P2249 【深基13.例1】查找 (洛谷)：最基本的二分查找练习。
P1873 [COCI 2011/2012 #5] EKO / 砍树：经典的“二分答案”题目。体会一下如何写 check 函数。
P1102 A-B 数对：尝试用“排序 + 二分”或者“Map”或者“双指针”三种方法解决它，这是理解时空权衡的绝佳题目。

到这里，你已经掌握了处理一维数组的绝大部分技巧。但如果数学老师问你：两个整数的最大公约数怎么算？素数怎么筛？

第 6 章：基础排序与查找 (Sorting & Searching)

算法竞赛入门

第 5 章：模拟与暴力枚举 (Simulation & Brute Force)

第 7 章：基础数论 (Basic Number Theory)