数据结构与算法 / 系统课时

识别二分答案的单调判定

识别二分答案的单调判定

有些题并不是在有序数组里找元素,而是在寻找“最小可行值”或“最大可行值”。只要候选答案能排序,并且某个判定函数会从假稳定地变成真,优化问题就能改写成判定问题,再用二分直接定位真假分界。

学习目标

  • 判断一个优化问题是否具有可二分的答案空间
  • 把“求最优值”改写成具有单调性的可行性判定
  • 用二分找到第一个满足条件的候选答案

先确认答案空间能否排序

二分答案的搜索对象不是原数组,而是所有可能的答案。第一步要问:候选答案能否按大小排成一条线,并且更大或更小的候选值之间存在稳定关系?

例如“在 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,当前速度就可行。

python
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))

预期输出:

text
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),这正是二分答案相比逐个枚举的主要收益。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

识别二分答案的单调判定

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通