二分答案时如何确定上下界？边界过大或过小会怎样？
简化版
二分答案前要先确定答案范围 [left, right]。
下界要保证答案不会比它更小，常来自最大单个需求、最小可能速度、最短时间。
上界要保证一定可行，常来自总和、最大值、最保守方案。
边界过小会漏答案，边界过大通常还能正确，但会增加二分次数。
详细版
二分答案不是对数组下标二分，而是对“答案值”二分。
所以第一步就是确定答案值域。
例如运送包裹：
- 船容量下界是
max(weights)，因为任何包裹都必须装下 - 船容量上界是
sum(weights)，因为一天运完一定可行
再如 Koko 吃香蕉：
- 速度下界是
1 - 速度上界是
max(piles)，因为每小时吃完一堆足够覆盖最保守情况
只要右边界一定可行，左边界不排除真实答案，二分就能收敛到最优值。
完整版教学
1. 二分答案为什么先看边界
普通二分查找通常直接有数组下标范围。
二分答案则没有现成数组，它的搜索区间要你自己构造。
如果边界错了，后面的判断函数再正确也没有意义。
二分答案的第一步不是写 while，而是证明真实答案一定在
[left, right]里。
2. 下界怎么找
下界是答案不可能低于的值。
常见来源包括：
- 单个任务的最小要求
- 数学上的最小值
- 题目约束给出的最小可选值
| 题目类型 | 下界示例 | 原因 |
|---|---|---|
| 运送包裹 | 最大包裹重量 | 船必须装得下最重包裹 |
| 吃香蕉速度 | 1 | 速度至少为正整数 |
| 分割数组最大和 | 数组最大值 | 每段至少包含一个元素 |
下界可以偏小，但不能大到超过真实答案。
3. 上界怎么找
上界要保证一定可行。
常见思路是构造一个“最保守但肯定能完成”的方案。
例如运送包裹时，一天把所有包裹运完，容量为总重量，一定可行。
const left = Math.max(...weights)
const right = weights.reduce((sum, x) => sum + x, 0)上界可以偏大，但不能小到排除真实答案。
如果上界偏大，最多多做几轮二分；如果上界偏小，结果会直接错。
4. 可行性函数要配合边界
二分答案通常写成找最小可行值：
function minFeasible(left, right) {
while (left < right) {
const mid = left + Math.floor((right - left) / 2)
if (canFinish(mid)) right = mid
else left = mid + 1
}
return left
}前提是：
canFinish(right)必须为真- 所有小于真实答案的值都不可行
- 所有大于等于真实答案的值都可行
这样才能找到第一个可行答案。
5. 边界过大或过小的影响
边界过大和过小的后果不一样。
边界过大：通常仍正确，只是多几轮 log 搜索
边界过小：可能把真实答案排除，直接错误比如真实答案是 10，但你把右边界设成 8，二分永远不可能返回 10。
而如果右边界设成 1000000，只要可行性单调，最终仍能收敛到 10。
6. 常见面试追问
- 误区：随便把左边界设为 0。 如果答案不允许为 0，虽然有时能跑，但语义不清，容易引出除零或死循环问题。
- 误区：上界不保证可行。 二分最小可行值时，右边界必须覆盖一个可行解。
- 误区：下界超过真实答案。 这会直接漏掉正确答案，无法靠后续二分修复。
- 追问：上界很大是否会超时？ 二分次数是
O(logV)，通常比线性试答案好得多。 - 追问：边界来自哪里？ 来自题目约束和一个能被证明的极端方案，而不是凭感觉。
能答出这些点，说明你真的理解二分答案。
7. 一个通用分析步骤
遇到二分答案题，可以按 4 步拆：
1. 答案是什么类型：容量、速度、时间、最大值？
2. 最小可能值是多少？
3. 最大一定可行值是多少？
4. can(mid) 是否从 false 单调变 true？只要这 4 个问题都清楚，代码通常就很顺。
8. 面试表达模板
可以这样说：
“二分答案前我会先证明答案范围。下界取任何解都不能低于的值，比如最大单个任务；上界取一个一定能完成的保守方案，比如总和。然后写 can(mid) 判断 mid 是否可行。如果可行，说明答案不超过 mid，收缩右边界；否则收缩左边界。边界偏大只影响 logV 次数，边界漏掉真实答案才是致命问题。”