分治与二分综合
本节目标
将排名排除、值域计数、抽屉原理和贪心验证组合起来，证明每一次二分都能安全缩小范围。
前面的二分题通常直接在下标或答案上搜索；综合题的难处在于，搜索对象会变成“第 k 小的排名”“未知的数值”或“允许的最大代价”。二分本身仍然只做一件事：依据一个可证明的判定，永久排除一半候选。这里要额外说清的是判定从何而来，以及排除为什么不会丢掉答案。
识别信号
出现以下信号时，应考虑把问题转成分治或值域二分：
- 多个有序部分共同决定第
k个位置，且一次可排除一个有序前缀； - 不能直接定位答案，但能统计“小于等于候选值”的元素个数；
- 数组元素落在有限整数范围内，计数结果能借助抽屉原理指向一半值域；
- 目标是最小化最大代价，并能按原顺序贪心验证给定上界是否可行。
不要先背诵循环写法。先确定搜索对象是排名、数值还是代价上界，再找出随候选值单调变化的计数或可行性。
问题模型
这四道题共享“候选空间加证明”的模型：
- 定义一个仍可能包含答案的区间或排名；
- 对当前候选计算比较、计数或所需资源；
- 用不变量证明一侧不可能含答案；
- 只保留另一侧，直到候选收敛。
中位数题的候选是两个有序数组中尚未排除的排名；矩阵与重复数题的候选是整数值域；分割数组题的候选是最大分段和。它们不能共享同一份代码模板，却共享同一份证明责任：每轮更新后答案仍留在区间中。
通用模板
值域二分适合“计数达到阈值”或“上界可行”的问题：
left = 合法候选的下界
right = 合法候选的上界
while left < right:
middle = left + (right - left) / 2
if predicate(middle):
right = middle
else:
left = middle + 1
return left
若 predicate(x) 表示“x 已经足够大”，它随 x 增大保持为真，循环找到第一个真值。矩阵题用“<= x 的数量至少为 k”；分割数组用“最大段和不超过 x 时所需段数不超过 k”。重复数题的计数方向相反：当 <= middle 的数量超过 middle，左半值域必含重复值。
排名排除不按固定数轴移动，而是比较两个长度相同的有序前缀边界。较小边界所在前缀中的元素都不可能是当前第 k 小，因此一次丢弃它并把 k 相应缩小。
模板变体
有序前缀排除
两个数组都还剩元素时，各取第 k / 2 个候选；较小候选及其前缀至多包含 k / 2 个不大于它的数，因而当前第 k 小不可能落在该前缀中。某一数组不足 k / 2 个元素时，把它的候选看作正无穷，优先排除另一边可用的前缀。
阶梯计数
行列递增矩阵从左下角开始：若当前值不大于候选值，该列上方全部满足，计入后右移；否则当前行右侧更大，应上移。一次计数只走 O(n) 步，而不是重新排序矩阵。
计数加抽屉原理
长度为 n + 1 的数组取值在 1..n，若前 middle 个数值盒子中装入的元素超过 middle 个，至少一个盒子装入两个元素。重复值就在左半值域；否则留在右半。
二分加贪心验证
给定最大段和，从左到右尽量把元素放进当前段；只有加入下一个元素会超限时才开新段。这种贪心得到达到该上界所需的最少段数。段数不超过 k 即可行。
母题序列
按拓展顺序练习四道题；它们依次训练排名排除、阶梯计数、抽屉原理和值域上界验证：
- 寻找两个正序数组的中位数 拓展：将中位数转成第
k小，并排除不可能的有序前缀。 - 有序矩阵中第 K 小的元素 拓展：在值域中二分，用阶梯路径计算不大于候选值的元素数。
- 寻找重复数 拓展：在数值范围内计数，用抽屉原理判断重复值所在半区。
- 分割数组的最大值 拓展：二分允许的最大分段和，并用贪心计算最少分段数。
常见误区
- 只写“数组有序所以能二分”，却没有证明被排除前缀或值域半区不含答案。
- 统计矩阵时逐个元素排序或使用堆，遗漏行列有序性带来的阶梯路径。
- 把重复数题的搜索区间写成数组下标，而不是
1..n的数值范围。 - 误以为分割数组必须先构造恰好
k段；验证“不超过k段”即可。 - 让累计和、候选上界或中点使用过窄整数类型，导致大输入时比较方向错误。
迁移方向
这组题把二分扩展为“证明驱动的范围缩减”。之后遇到多路有序数据，可继续寻找能一次排除整段候选的比较；遇到最小化最大值问题，先写出单调可行性，再考虑二分；遇到计数阈值问题，则先证明计数函数的单调性。快慢指针、堆和动态规划也能解决其中部分题目，但它们属于不同的模型，应在需要对应结构或状态时再选择。