直接回答:二分答案是在答案的取值空间上二分,而不是在有序数组上二分:把“求最优值”转化为“判定某个值是否可行”的判定问题(check(x)),若可行性随 x 单调(x 可行则更大/更小的都可行),就能在 [lo, hi] 上二分,复杂度 O(log(range) × check)。经典题:爱吃香蕉的珂珂(最小速度)、运送包裹的最小载重、分割数组的最大值最小化。
展开解析:适用判据两条:答案空间可枚举出上下界(载重在 [max(货物), sum(货物)]);存在单调的 check 函数——通常贪心或模拟验证,O(n) 可判。解题模板:确定“最大化最小值”还是“最小化最大值”的语义,写好 check 后用统一的闭区间二分模板(while lo < hi,按方向取中点收缩),避免边界死循环。常见坑:check 写反单调方向导致答案取错侧;上下界估计太宽虽然只多 log 次但 check 里有乘法时注意溢出(用 64 位);浮点答案二分改用固定迭代次数(100 次足够到 1e-9 精度)而非比较区间长度。思维价值:二分答案把最优化问题降维成判定问题,判定总比优化好做——这与参数化搜索(parallel binary search)、分数规划同属一族。识别训练:看到“最小化最大的某某”“最大化最小的某某”“最少的某某使得满足条件”就先把 check 写出来,能写出单调 check 即锁定二分答案。
追问方向:check 函数本身带二分时怎么处理(二重二分)?答案在整数域但 check 是概率性的怎么办?
(约 460 字)