数据结构与算法 / 系统课时
识别二分答案的单调判定
识别二分答案的单调判定
有些题并不是在有序数组里找元素,而是在寻找“最小可行值”或“最大可行值”。只要候选答案能排序,并且某个判定函数会从假稳定地变成真,优化问题就能改写成判定问题,再用二分直接定位真假分界。
学习目标
- 判断一个优化问题是否具有可二分的答案空间
- 把“求最优值”改写成具有单调性的可行性判定
- 用二分找到第一个满足条件的候选答案
先确认答案空间能否排序
二分答案的搜索对象不是原数组,而是所有可能的答案。第一步要问:候选答案能否按大小排成一条线,并且更大或更小的候选值之间存在稳定关系?
例如“在 h 小时内吃完所有香蕉的最小速度”中,速度 k 可以按 1, 2, 3, ... 排序。速度越大,完成任务所需时间只会减少,不会突然又增加,因此答案空间天然有序。
只有“答案可以排序”还不够。真正决定能否二分的是:对候选答案执行一次可行性判定后,结果必须形成连续的真假区间,而不能出现 false → true → false 这样的反复变化。
把最优化改写成真假判定
设 check(k) 表示“速度为 k 时,是否能在限定时间内完成”。对于最小速度问题,通常会得到这样的序列:
false, false, ..., false, true, true, ..., true
我们不再直接计算“最小速度是多少”,而是寻找第一个令 check(k) 为 true 的位置。这一步就是二分答案的核心转换。

以香蕉问题为例,如果 k = 3 无法按时完成,而 k = 4 可以,那么所有大于 4 的速度也一定可以。于是 4 就是从不可行区进入可行区的边界。
用主示例找到第一个可行速度
下面实现经典的“最小吃香蕉速度”。对于速度 speed,每堆香蕉需要的小时数是向上取整的 pile / speed。只要总小时数不超过 h,当前速度就可行。
from typing import List
def min_eating_speed(piles: List[int], h: int) -> int:
def can_finish(speed: int) -> bool:
hours = 0
for pile in piles:
# 整数写法完成向上取整,避免浮点误差。
hours += (pile + speed - 1) // speed
return hours <= h
left, right = 1, max(piles)
# 区间始终保留最终答案;可行时继续向左寻找更小值。
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
right = mid
else:
left = mid + 1
return left
if __name__ == "__main__":
print(min_eating_speed([3, 6, 7, 11], 8))预期输出:
4这里搜索区间是 1 到 max(piles)。上界一定可行,因为速度等于最大堆大小时,每堆最多耗费一小时;题目存在解时,真正答案不会超过这个值。
当 can_finish(mid) 为 true 时,mid 可能已经是答案,但还需要检查左侧是否存在更小的可行值,所以保留 mid 并令 right = mid。如果判定为 false,则 mid 及其左侧都不可能成为答案,可以直接令 left = mid + 1。
识别最小真与最大真
刷题时可以把二分答案进一步归纳成两个方向。若判定结果随候选值增大呈 false → true,通常寻找最小可行值;若呈 true → false,通常寻找最大可行值。
常见信号包括“最小容量”“最小速度”“最短时间上限”“最大化最小值”“最小化最大值”。看到这类目标时,不要先尝试枚举所有答案,而应优先构造一句清晰的判定:给定候选值 x,能否在约束内完成任务?
最后再检查两件事:判定函数是否足够快,以及真假是否真的单调。若单次判定复杂度为 O(n),答案范围大小为 R,整体通常可以做到 O(n log R),这正是二分答案相比逐个枚举的主要收益。