什么是「二分答案」？如何在答案空间上二分（求平方根、最小化最大值）？

简化版

「二分答案」是把二分用在答案的取值范围上,而不是给定的数组上。适用条件:答案具有单调性——存在一个「临界值」,小于它都不可行(或都可行)、大于它都可行(或都不可行)。做法:在 [最小可能答案, 最大可能答案] 上二分,写一个 check(x) 判断「x 是否可行」,根据结果收缩,逼近临界值。典型如求平方根、Koko 吃香蕉、分割数组最大值最小化。

详细版

通用框架:

int binarySearchAnswer(int lo, int hi) {  // 答案的取值范围
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;          // mid 可行，尝试更小（求最小可行解）
        else lo = mid + 1;                 // mid 不可行，答案更大
    }
    return lo;   // 最小的可行答案
}

例:求整数平方根(x 的最大整数 k 使 k² ≤ x)

int mySqrt(int x) {
    long lo = 0, hi = x;
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2;   // 上取整（求最大可行解）
        if (mid * mid <= x) lo = mid;         // 可行，尝试更大
        else hi = mid - 1;
    }
    return (int) lo;
}

关键三步:①确定答案范围 [lo, hi];②写 check(x) 判可行;③根据「求最小/最大可行解」选收缩方向和 mid 取整。

完整版教学

一、什么是二分答案:换个对象二分

普通二分是「在有序数组里找一个值」。二分答案是「在答案的取值范围里找那个最优答案」。它的思维转换是:不去直接算答案,而是「猜一个答案,验证它可不可行」,通过二分不断逼近临界。 只要「可行性」随答案单调变化,就能二分。这类题的信号是:「求最大的……使得……」「求最小的……使得……」「最小化最大值 / 最大化最小值」。

二、适用的核心前提:单调性

二分答案能成立,靠的是答案空间的单调性——必须存在一个临界值,把答案空间分成「可行」和「不可行」两段:

不可行 不可行 不可行 | 可行 可行 可行     （求最小可行解，找左边界）
                    ↑ 临界值 = 答案
可行 可行 可行 | 不可行 不可行 不可行       （求最大可行解，找右边界）
              ↑ 临界值 = 答案

只要 check(x) 满足「一旦 x 可行,所有比它大(或小)的也可行」,单调性就成立,就能二分。判断能不能用二分答案,就是判断有没有这种单调性。

三、三个关键要素

写二分答案,想清楚三件事:

答案范围 [lo, hi]:答案最小可能是多少、最大可能是多少。范围要能覆盖真实答案,可以宽松(比如求平方根 hi 取 x)。
check(x) 判可行:给定一个候选答案 x,能否满足题目约束?这是二分答案的灵魂,通常是一个 O(n) 的遍历/贪心。
收缩方向 + mid 取整:求「最小可行解」→ 可行时 hi = mid(往小试)、mid 下取整;求「最大可行解」→ 可行时 lo = mid(往大试)、mid 上取整(防死循环)。

四、经典例题拆解

① 求平方根:找最大的整数 k 使 k² ≤ x。答案范围 [0, x],check(k) = (k*k <= x),求最大可行解,mid 上取整。

② Koko 吃香蕉(LeetCode 875):每小时最多吃 speed 根,求能在 h 小时内吃完所有香蕉的最小速度。答案范围 [1, max(piles)],check(speed) = 「以此速度吃完需要的小时数 ≤ h」(遍历所有堆求耗时,O(n))。速度越大越容易吃完 → 单调,求最小可行解。

③ 分割数组的最大值(LeetCode 410):把数组分成 k 段,最小化「各段和的最大值」。答案范围 [max(nums), sum(nums)],check(limit) = 「以 limit 为每段上限,贪心分割所需段数 ≤ k」。limit 越大越容易分成更少段 → 单调,求最小可行解。

这三题结构完全一样:定范围 → 写 check(遍历/贪心) → 二分求最小/最大可行解。

五、复杂度

时间 O(n · log(答案范围)):二分答案空间 log(hi-lo) 次,每次 check 是 O(n)。
相比暴力枚举所有答案 O(n · 范围),二分把「范围」这一维从线性降到对数,通常是从超时到 AC 的关键。

这里的 n 是一次可行性检查的代价，答案范围才决定二分轮数。例如容量范围是 1 到 10^9 时大约检查 30 次，总复杂度是 O(30n)，不能把它误写成只与数组长度有关的 O(log n)。

六、怎么识别一道题能用二分答案

看到这些特征,优先考虑二分答案:

「最小化最大值」「最大化最小值」——几乎是二分答案的标志。
「求满足某条件的最小/最大的 x」,且「x 越大越容易/越难满足」(单调)。
直接求答案很难,但「给定答案验证可行性」很容易(能写出 O(n) 的 check)。

把「求解」转成「判定 + 二分」,是这类题的通用突破口。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：可行性谓词 P(x) 在答案空间上单调，边界点就是所求答案。

对应的状态推进是：猜一个答案 mid，用 check(mid) 判断后保留仍可能包含最优值的一侧。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。总时间 O(check成本 × log(答案范围或精度步数))。

带数字走一遍：在 1..1000 中找最小可行容量最多约 10 次 check。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	必须能定义单调可行性，不能仅因答案是数字就二分
时间复杂度	O(C log R)，C 为 check 复杂度
额外空间	通常 O(1)，不含 check 内部空间
关键边界	整数最小可行与最大可行的收缩方向不同；浮点需规定误差或迭代次数
替代方案	范围很小可枚举，存在直接公式时不要二分

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“必须能定义单调可行性，不能仅因答案是数字就二分”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(C log R)，C 为 check 复杂度就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“总时间 O(check成本 × log(答案范围或精度步数))”。
误区：重复值和边界值不会改变代码。 整数最小可行与最大可行的收缩方向不同；浮点需规定误差或迭代次数。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“可行性谓词 P(x) 在答案空间上单调，边界点就是所求答案”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“在 1..1000 中找最小可行容量最多约 10 次 check”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“范围很小可枚举，存在直接公式时不要二分”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

二分答案 = 在答案的取值范围上二分(而非数组),前提是答案有单调性(存在临界值把答案分成可行/不可行两段)。三要素:①定答案范围 ②写 check(x) 判可行(通常 O(n) 遍历/贪心) ③选收缩方向(求最小可行解→可行时 hi=mid;求最大可行解→可行时 lo=mid 且 mid 上取整防死循环)。识别信号:「最小化最大值/最大化最小值」「求满足条件的最小/最大 x」。复杂度 O(n·log 范围)。经典:平方根、Koko 吃香蕉、分割数组最大值。

简化版

详细版