二分答案

查找 · 答案空间上的二分 · 最小可行解

数组没了，也能二分

经典题：4 堆香蕉 [3, 6, 7, 11]，警卫 8 小时后回来，珂珂每小时只能吃一堆里的 k 根——最小时速 k 是多少？没有现成的数组可查，但把候选答案排成一排（速度 1..11），奇妙的事发生了：速度越快越可能吃完，可行性关于答案单调—— ✗ ✗ ✗ ✓ ✓ ✓ …。「找第一个 ✓」，这不就是二分边界里的 lower_bound 吗？

柱子这回是答案本身

下面的柱子不是被查数组，而是 11 个候选速度。每一步试探 mid：现场算 Σ ⌈pile / k⌉ 与 8 比——可行就「答案还能更小」收 hi，不可行就「只能加速」抬 lo；相遇点即最小可行速度 4（恰好 8 小时，慢一档就 10 小时超时）。右侧代码随每一步同步高亮。

数组没了也能二分！4 堆香蕉 [3, 6, 7, 11]，8 小时内吃完的最小时速是多少？把候选答案排成一排——这 11 根柱子就是速度 1..11。速度越快越可行（单调 ✗✗✗✓✓…），找「第一个可行」即可

什么时候能「二分答案」

三要素：①答案空间有界（如 [1, max]）；②可行性关于答案单调；③单点可行性可验（一个 O(n) 的 check）。
复杂度：O(check × log(答案空间))——把「求最优」降成「验可行」。
找最大可行：谓词方向反过来（✓✓✓✗✗），找最后一个 ✓ = upper 侧模板。
实数版：答案是实数时二分固定次数（如 100 轮）或到精度 ε。

「最小化最大值 / 最大化最小值」一族几乎全是它：分割数组的最大段和最小化、D 天内送达的最低运载能力、切木材求最长段、会议室最少数量……凡是答案越大越可行（或越不可行）的题，先想二分答案。至此查找大类四页收官：找值 → 找边界 → 断崖找值 → 找答案——二分的四重境界。