为什么先学排序和二分
上一篇把复杂度、输入输出和代码模板准备好了，这一篇进入第一个真正高频的基础工具：排序与二分。
排序看起来只是把数组排一下，二分看起来只是查一个数。但在 ACM 里，它们经常是把一道题从暴力枚举变成可做算法的第一步。
很多问题本来是乱的：数值乱、位置乱、时间乱、区间乱。排序做的事情，就是先给这些对象建立一个顺序。顺序一旦建立，后面就可能出现“左边都满足、右边都不满足”这样的结构，二分就有了用武之地。
排序先解决顺序问题
C++ 里最常用的是 sort。默认从小到大排序：
vector<int> a = {3, 1, 4, 1, 5};
sort(a.begin(), a.end());如果要从大到小，可以写比较器：
sort(a.begin(), a.end(), [](int x, int y) {
return x > y;
});排序结构体时，比较器要明确你最关心的字段。比如区间先按左端点升序，再按右端点升序：
struct Segment {
int l, r;
};
sort(seg.begin(), seg.end(), [](const Segment& a, const Segment& b) {
if (a.l != b.l) return a.l < b.l;
return a.r < b.r;
});比较器最重要的一点是保持一致性。不要写出一会儿认为 a < b，一会儿又认为 b < a 的逻辑，否则排序结果会变得不可控。
排序之后能做什么
排序之后，常见的变化有几类。
- 去重：先排序，再用
unique把重复元素压掉； - 找相邻差值：最小差值通常会出现在排序后的相邻元素之间；
- 贪心选择：活动安排、区间覆盖、会议室这类题经常先按某个维度排序；
- 配对：一个最小配一个最大，或者两个指针从两头往中间走；
- 离散化：把很大的值域压成较小的排名。
所以看到题目里有“大小关系”“排名”“最近”“第 k 个”“区间端点”“时间先后”，都可以先想一下排序会不会让结构变清楚。
二分查找先写稳
在有序数组里查找，可以直接用标准库。
auto it = lower_bound(a.begin(), a.end(), x); // 第一个 >= x 的位置
if (it != a.end() && *it == x) {
int pos = it - a.begin();
}lower_bound 找第一个大于等于 x 的位置，upper_bound 找第一个大于 x 的位置。它们常用来统计某个数出现了多少次：
int cnt = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x);自己写二分时，我更推荐先掌握“找第一个满足条件的位置”这一种模板。
int l = 0, r = n - 1;
int ans = n;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}这个模板背后的意思是：如果 mid 满足条件，答案可能就是它，也可能在更左边；如果不满足，答案只能去右边找。
二分答案看单调性
二分不只能在数组里找数，还能在答案范围里找答案。这叫二分答案。
判断能不能二分答案，关键不是题目里有没有数组，而是有没有单调性。也就是说，如果某个答案 x 可行，那么比它更大或更小的一侧是不是一定也可行。
比如“最小化最大值”经常可以二分：给一个上限 x，检查能不能在这个限制下完成任务。如果 x 可以完成，那么更大的上限通常也可以完成，于是可行区间是连续的。
bool check(int limit) {
// 判断 limit 作为答案是否可行
}
int l = 0, r = 1e9, ans = r;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}二分答案时，真正难的往往不是二分模板，而是 check 怎么写。check 通常会结合贪心、前缀和、图论或动态规划。
最容易错的地方
- 边界写错：到底是找第一个满足，还是最后一个满足；
mid = (l + r) / 2可能溢出，稳妥写法是l + (r - l) / 2；check没有单调性，却硬套二分；- 排序比较器写得不稳定，导致结果不符合预期；
- 二分浮点答案时精度和循环次数没有控制好。
我自己的习惯是：写二分前先在纸上画一条线，标出“不满足”和“满足”的分界点。能画出来，模板就不容易写乱。
这一篇先记住什么
- 排序的价值不是“排好看”，而是制造顺序。
- 二分的本质不是“折半查找”，而是利用单调性缩小范围。
- 遇到最小化最大值、最大化最小值、是否可行这类问题，要主动想二分答案。
下一篇继续学一个非常基础但很强的工具：前缀和与差分。它们解决的是“区间反复求”和“区间反复改”的问题。