二分答案解题框架
本节目标
把最优化目标改写为具有单调性的可行性判断，在答案范围内寻找第一个可行值。
普通二分在有序数据中寻找位置，二分答案则在一段有序的候选答案中寻找边界。题目往往没有直接给出这个有序数组；我们需要自己确定答案范围，并写出一个随答案变化具有单调性的可行性函数。
识别信号
遇到下列组合时，应优先考虑二分答案：
- 题目要求“最小化最大值”或“最大化最小值”；
- 给定一个候选答案后，可以较快判断它是否满足限制；
- 候选值变大或变小时，可行性只会朝一个方向变化；
- 答案是整数，且上下界容易从输入中推出。
先问“答案为 x 时能否完成”，通常比直接构造最优方案更容易。
问题模型
把候选答案记为 x，定义布尔函数 check(x)。以“求最小可行值”为例：
x 太小：false false false
答案： true
x 更大： true true true
只要能证明 check(x) 从假到真至多变化一次，问题就转化为：在闭区间 [left, right] 中寻找第一个令 check(x) 为真的整数。
四个核心步骤是：
- 答案范围：确定所有可能答案的下界
left与上界right； - 可行性函数：实现
check(x)，只回答候选值是否可行； - 单调性证明：说明可行性为什么只会朝一个方向变化；
- 边界二分：寻找第一个可行值或最后一个可行值。
通用模板
求最小可行值时，维护闭区间 [left, right]，并保证真实答案始终在区间中：
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
当 check(mid) 为真时，mid 可能就是答案，不能把它排除，所以令 right = mid；为假时，mid 一定不是答案，令 left = mid + 1。区间最终收缩到一个值，它就是第一个可行答案。
模板变体
如果题目要求“最大的可行值”，可把真假区间看成：
true true true | false false false
此时寻找最后一个真值，中点应向上取整，避免只剩两个数时无法收缩：
mid = left + (right - left + 1) // 2
if check(mid):
left = mid
else:
right = mid - 1
二分答案的变化通常集中在三处：答案上下界、check 的含义，以及要找第一个真值还是最后一个真值。循环结构本身应保持稳定。
母题序列
建议按必学顺序练习：
- 爱吃香蕉的珂珂 必学：用向上取整计算固定速度所需时间，建立最小可行值模型。
- 在 D 天内送达包裹的能力 必学：把贪心分组封装为可行性判断，理解二分与贪心的组合。
常见误区
- 没有证明单调性，只因题目出现“最小”或“最大”就套二分。
- 上下界不是保证可行的完整范围，真实答案可能一开始就在区间外。
check同时修改输入或构造最终方案，使判断逻辑难以验证。- 求第一个真值时写成
right = mid - 1，错误排除可能的答案。 - 计算中点、总和或累计时间时使用过窄整数，尚未比较就已经溢出。
- 用浮点除法再取整，给大整数边界引入精度风险。
迁移方向
掌握“答案范围 + 可行性函数 + 单调性 + 边界二分”后，可以继续处理分割数组、最小运输能力、最短完成时间、最大化最小间距等问题。它们表面上分别涉及数组分段、调度或放置，核心都在于：先把最优值固定为候选答案，再用线性扫描回答是否可行。