外观
二分答案法一文搞懂：边界处理与「最小化最大值」题型套路实测
很多人对二分的认知停留在「在有序数组里找一个数」，遇到「把数组分成 k 段使最大段和最小」「切割电缆使长度最大化」这类题时完全想不到二分。实际上二分的适用面要宽得多：只要能构造一个判定问题「答案为 x 是否可行」，并且可行性随 x 单调变化——x 可行则更小的 x 都可行（或都不可行，看方向）——那么答案空间就是一个隐形的有序数组，照样可以二分。这就是「二分答案」：对答案本身二分，而不是对输入序列二分。
这类题目的标识性问法很固定：「最小的最大值」「最大的最小值」「最多能拿到多少」「至少需要多少天」。看到这些措辞，先别急着贪心或动态规划，花一分钟验证单调性，往往一条二分答案的路就近在眼前。真正的难点不在二分骨架，而在三处边界：检验函数怎么写、循环怎么收敛、最后答案是 lo 还是 lo 减一。这篇文章围绕这三处展开。
思路推导：把「求最优」翻译成「判可行」
以经典场景为例：n 根电缆要切成 k 段等长（或各取一段）给 k 台设备，求每段最大可能的长度。设长度为 x，问题变成判定「按长度 x 能切出至少 k 段吗」——对每根电缆能切出的段数是 floor(len / x)，累加后与 k 比较。这个判定函数关于 x 单调递减：x 越大越切不出 k 段。于是答案空间 [0, max_len] 上存在一个临界点，左侧全部可行、右侧全部不可行，二分要找的就是临界点本身。
「最小化最大值」方向同理且更常见：把数组分成 k 个非空连续子数组，使各子数组和的最大值尽可能小。设上限为 x，判定「能否分成不超过 k 段且每段和不超过 x」——贪心扫描，能装就装、装不下就开新段，统计段数与 k 比较。x 越大越容易满足，判定函数单调递增，临界点即所求的最小可行上限。两个方向共用同一套骨架，差异只在检验函数的写法和收敛后的取值。
| 方向 | 典型问法 | 检验函数单调性 | 收敛目标 |
|---|---|---|---|
| 最大化最小值 | 切割长度、运输船载重 | x 越大越难满足 | 最后一个可行的 lo |
| 最小化最大值 | 分段上限、完成时限 | x 越大越易满足 | 最后一个可行的 lo |
方向感混乱时有一个可靠的自检方法：先固定 x=边界极值，确认检验函数在该端的取值（一端必须恒可行、另一端恒不可行），再确认单调方向与「可行区在哪一侧」。这三问答清楚，代码里的初始化和收敛分支自然就定下来了。
实操代码：两个方向的完整实现
先写「最小化最大值」的代表题，分割数组使最大子数组和最小。检验函数用贪心：从左到右累加，超过上限就开新段；段数不超过 k 即可行。二分区间左端取数组最大元素（下限，任何合法分割的段和都不小于它），右端取全部元素之和（上限，单段一定可行）：
python
# 分割数组的最大值最小化：二分答案 + 贪心检验（Python）
def split_array(nums: list[int], k: int) -> int:
def feasible(limit: int) -> bool:
"""检验：能否分成不超过 k 段且每段和不超过 limit"""
segments, current = 1, 0 # 至少一段，current 为当前段累加和
for num in nums:
if current + num > limit: # 当前段装不下，开新段
segments += 1
current = num
if segments > k: # 提前剪枝，段数已超限
return False
else:
current += num
return True # 扫描完成段数未超限，可行
lo, hi = max(nums), sum(nums) # 可行性两端：下限必不可行（若 k>1），上限必可行
while lo < hi: # 收敛条件：区间只剩一个候选值
mid = lo + (hi - lo) // 2 # 防溢出写法，习惯在 C/Java 中同样成立
if feasible(mid): # mid 可行，更小的值可能也可行
hi = mid # 保留 mid，向左压缩
else: # mid 不可行，答案必须更大
lo = mid + 1 # 排除 mid，向右压缩
return lo # 收敛后 lo 即最小可行上限收敛规则与模板严格对应：hi = mid 表示「mid 本身可能是答案，不能丢」，lo = mid + 1 表示「mid 已被判定不可行，坚决排除」。只要这两个赋值保持这个语义、循环条件用 lo < hi，循环必然在 lo == hi 处终止且该点就是临界答案——这套约定下不存在「答案是 lo 还是 lo−1」的纠结，纠结只发生在混用其他模板的时候。
再看「最大化最小值」方向，用电缆切割为例：把每根电缆切成若干整数长度段，使能得到的不少于 k 段的最大段长最大。检验函数对每根电缆累加 floor(len / x)，判断总段数是否达标。注意二分上界是最长电缆而非总长，下界从 1 开始（整数长度）：
python
# 电缆切割：最大化最小方向（此处为最大化段长）的二分答案（Python）
def max_cable_length(cables: list[int], k: int) -> int:
def pieces_at_length(x: int) -> int:
"""按长度 x 能切出的总段数，x 越大段数越少"""
return sum(length // x for length in cables) # 整除即段数
lo, hi = 1, max(cables) # 段长候选区间：[1, 最长电缆]
while lo < hi:
mid = lo + (hi - lo + 1) // 2 # 上取整偏移：mid+1 存在时避免死循环
if pieces_at_length(mid) >= k: # mid 可行，尝试更大的段长
lo = mid # 保留 mid，向右压缩
else: # mid 不可行
hi = mid - 1 # 排除 mid，向左压缩
return lo # 收敛后 lo 即最大可行段长这段代码里最值得盯的一行是 mid = lo + (hi - lo + 1) // 2：当收缩分支是 lo = mid 时，mid 必须上取整偏移。原因很具体——区间剩两个元素 [lo, lo+1] 时，若 mid 取到 lo 且 mid 可行，lo = mid 之后区间纹丝不动，直接死循环；上取整让 mid 落在 lo+1 上，区间严格缩小。死循环十有八九出在这里，写完先在两元素区间上心算一轮。
复杂度层面，两题结构相同：检验函数一次 O(n) 扫描，二分轮数 O(log V)，V 是答案空间的宽度（总段长或元素和上界），总复杂度 O(n log V)。对 10⁵ 量级的数据，V 即使到 10¹⁴，log V 也只有四十多轮，完全可行——这正是二分答案的价值：把一个看似需要搜索或 DP 的问题压缩成「线性检验 + 对数轮次」的组合。
边界与避坑总结
- 先验证单调性再动手。二分答案的全部正确性押在「可行性随 x 单调」上；如果检验结果随 x 非单调（存在可行—不可行—可行的振荡），模板给出的临界点没有意义，先重新构造判定问题。
- 检验函数比二分骨架更容易错。贪心检验的「能装就装」策略必须论证贪心选择不影响后续可行性；分段类问题里「装不下才开新段」是最优的，因为提前断段只会让后续更宽松，想不清这一点就不要套贪心。
- 两元素区间的 mid 偏移要手算。lo = mid 分支配上取整、hi = mid 分支配下取整；混用或漏配是死循环的头号来源，写完在 [x, x+1] 的极小区间上模拟一轮即可暴露。
- 边界初始化要有「一端恒可行」。下界与上界必须覆盖整个答案空间且使检验函数在两端分别恒不可行/恒可行（按方向），否则临界点可能落在区间外被漏掉；分割题的下界取 max(nums) 而不是 0，0 会让检验函数除零或恒假。
- 实数二分用固定迭代次数而不是精度判断。浮点误差会让 while right - left > eps 类的写法在极端用例上震荡；直接循环一百次左右，log₂(区间宽度) 覆盖精度需求即可，输出时再按题目要求保留小数。
二分答案的通用性常被低估：从资源分配、进度安排到阈值搜索，只要能写出单调的检验函数，它就是最省脑力的首选方案。判断题型的肌肉记忆可以总结成一句话——「问最值、可判定、有单调」三条件齐备，先写检验函数，骨架是背下来的部分，检验才是动脑的部分。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。