二分答案（Binary Search on Answer）

1. 核心原理

二分答案（binary search on answer）解决一类形如"求最优 X"的问题：题目要找一个使某条件成立的最大或最小整数（或浮点数），而这个 X 关于"是否可行"具有单调性——一旦 X = c 可行，所有 X ≥ c（或 ≤ c）也都可行。二分对象从数组下标搬到答案的值域，骨架仍是 lower_bound。

暴力枚举答案为什么炸

直觉做法是：候选答案 X 从值域下界开始一个一个往上试，每个 X 调用一次 O(n) 判定函数 check(X)。值域大小 V 可能高达 10⁹，外层枚举一次的总复杂度变成 O(n · V) ≈ 10⁴ × 10⁹ = 10¹³——LC 单测 1 秒上限是 10⁸ 量级，TLE 五个数量级。

check(X) 这一步 O(n) 没问题，卡脖子的是外层"一个一个 X 试"。如果能把外层从 O(V) 砍成 O(log V)，整体就降到 O(n log V) ≈ 10⁴ × 30 = 3 × 10⁵，秒过。

算法的关键洞察

观察判定函数 check(X) 的单调性。以 LC 1011 装船问题为例：

如果载重 cap = c 能在 days 天内运完，那么 cap = c + 1 也一定能在 days 天内运完。

直觉是船更大只会更轻松；严格证明用包含论证：用更大的 cap 重新跑一次贪心，每天能装的包裹只多不少，总天数只减不增。

这意味着 check(X) 关于 X 是个单调函数：从左到右一片 False，然后翻成一片 True，中间夹着一条翻转边界。这条边界就是答案——第一个让 check 变 True 的 X。

整段值域被切成"红色不可行 + 蓝色可行"两片，二分就是在找这条 False → True 的翻转边界。形态正是上一章的 lower_bound——直接套模板，唯一变的只是二分对象从下标搬到了值域。

抽象成一句话：

把题目"求最优 X"翻译成"对候选 X 写一个单调的 check(X)"。check 返回 True 的 X 构成一段后缀（或前缀），二分这段后缀的最左端（或前缀的最右端）就是答案。

套路类型一览

二分答案题通常带有以下信号之一，识别命中两三条即可上模板：

check(X) 的实现根据题目分为五大类，本章后面会逐一展示：

• 贪心扫一遍：LC 1011 / 410（顺序切段、超阈值开新段）
• 排序 + 贪心：LC 2517（选 k 个 / 间距问题）
• 数学公式：LC 1760 / LC 875（每元素独立用 ⌈x/k⌉ 计数）
• 前缀和 + 双指针：LC 644（子数组和 / 平均值）
• BFS / Dijkstra：LC 1631（图上找路径阈值）

注意：不是所有"求最优"都能二分答案。识别时先验单调性，再套模板。

哪些题看着像但不能二分答案

常见三类"看起来像但不行"的情况：

• check 不单调。题目要"恰好等于 k"——count(x) == k 不是单调的（count 函数本身单调，但"相等"不单调）。这类通常转化成"找第一个 count(x) >= k"再做后处理。
• 答案不是一个数。题目让你返回一个"区间"或"路径"，没有自然的值域可二分。这时要把"区间长度"或"路径权重"提出来当二分对象。
• 问题本身 NP-Hard。某些题表面像"分配 / 调度"——"把任务分给 m 台机器使最大完成时间最小"——一般情形下 m ≥ 2 时是多机调度 NP-Hard。这时如果"严格非连续"地分配，二分答案 + 贪心判定不保证最优，只能给近似解（如 LPT 的 4/3 近似）。若题目额外要求"按数组顺序连续切"（如 LC 410），退化成 P 问题，二分答案可解。

2. 通用模板

二分答案的骨架一字不差地继承上一章的 lower_bound，区别只在判定函数：从 nums[mid] >= target 换成由题目派生的 check(mid)。值域上下界是这一族的新关键——上下界必须包住真实答案，给错任意一边二分直接废。

def binary_search_on_answer(lo: int, hi: int, check) -> int:
    """
    在值域 [lo, hi) 上找最小的 x 使 check(x) 为 True。
    要求 check 关于 x 单调（一旦为 True，更大的 x 也都为 True）。
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid                  # mid 可能就是答案，往左收
        else:
            lo = mid + 1              # 还不可行，往右
    return lo


# 最大化方向（找最大的 x 使 check(x) 为 True）的镜像模板
def binary_search_max(lo: int, hi: int, check) -> int:
    """在 [lo, hi] 闭区间上找最大的 x 使 check(x) 为 True。"""
    while lo < hi:
        mid = (lo + hi + 1) // 2      # 上取整！防 lo, hi = x, x+1 时死循环
        if check(mid):
            lo = mid                  # 保留 mid 作为候选下界
        else:
            hi = mid - 1
    return lo

// 最小化方向：找最小的 x 使 check(x) 为 True
int binarySearchOnAnswer(int lo, int hi, IntPredicate check) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check.test(mid)) hi = mid;        // mid 可能是答案
        else lo = mid + 1;                    // 还不可行
    }
    return lo;
}

// 最大化方向：找最大的 x 使 check(x) 为 True
int binarySearchMax(int lo, int hi, IntPredicate check) {
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;     // 上取整防死循环
        if (check.test(mid)) lo = mid;        // 保留 mid 候选
        else hi = mid - 1;
    }
    return lo;
}

// 最小化方向：找最小的 x 使 check(x) 为 True
int binarySearchOnAnswer(int lo, int hi, function<bool(int)> check) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;             // mid 可能是答案
        else lo = mid + 1;                    // 还不可行
    }
    return lo;
}

// 最大化方向：找最大的 x 使 check(x) 为 True
int binarySearchMax(int lo, int hi, function<bool(int)> check) {
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;     // 上取整防死循环
        if (check(mid)) lo = mid;             // 保留 mid 候选
        else hi = mid - 1;
    }
    return lo;
}

模板的几个关键点：

• 值域上下界：lo 取"理论最小可行答案"，hi 取"理论最大可行答案 + 1"（左闭右开）。LC 1011 取 [max(weights), sum(weights) + 1)——下界保证单个包裹装得下，上界保证最坏一天能全装完。给错任意一边二分直接废。
• mid 取法：mid = lo + (hi - lo) / 2 防溢出；Java / C++ 里当 lo + hi > INT_MAX 时 (lo + hi) / 2 会溢出，Python 整数无此问题但跨语言移植时统一写防溢出版本更稳。
• 最小化 vs 最大化方向的镜像：找最小用下取整 + hi = mid，找最大用上取整 + lo = mid。上取整 mid = (lo + hi + 1) / 2 防止 lo, hi = x, x + 1 时 mid = lo 导致死循环。
• 浮点二分：浮点版本（如 LC 644）用闭区间 [lo, hi] + 固定迭代次数（通常 100 次），不要写 while hi - lo > eps——浮点累积误差可能让循环不收敛。100 次迭代覆盖 2¹⁰⁰ 倍精度收缩，远超 IEEE 754 双精度尾数的需求。

3. 母题精讲

上一章把二分立在了"下标"上：数组有序，从左到右单调。这一章把二分搬到一个更抽象的对象——答案本身。下面从 LC 1011 出发立模板。

LeetCode 1011. 在 D 天内送达包裹的能力

链接：LeetCode 1011

题意：传送带上有 n 个包裹，第 i 个重 weights[i]。船一天能装总重不超过载重 cap 的若干个包裹，且包裹要按数组顺序装（不能跳过、不能重排）。给一个天数 days，返回能够在 days 天内运完所有包裹的最小船载重。

数据范围：

• weights.length = n：1 到 5 × 10⁴
• weights[i]：1 到 500
• days：1 到 n

示例：

输入：weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
输出：15
解释：
day 1: 1 + 2 + 3 + 4 + 5 = 15
day 2: 6 + 7 = 13
day 3: 8
day 4: 9
day 5: 10
载重 14 不行（第 1 天就装不下前 5 个），15 是最小值。

先把暴力解写出来

直觉解：候选 cap 从最小可能值开始，一个一个往上试。每个 cap 都模拟一次——扫一遍 weights，累加和；累加超过 cap 就开新一天。统计总天数 ≤ days 则可行。

class Solution:
    def shipWithinDays_brute(self, weights: list[int], days: int) -> int:
        def can_ship(cap: int) -> bool:
            d, cur = 1, 0
            for w in weights:
                if w > cap:
                    return False             # 单个包裹超载，永远不行
                if cur + w > cap:
                    d += 1
                    cur = w
                else:
                    cur += w
            return d <= days

        for cap in range(max(weights), sum(weights) + 1):
            if can_ship(cap):
                return cap
        return sum(weights)

时间 O(n × (sum(w) − max(w)))、空间 O(1)。can_ship 本身 O(n)，外层枚举 cap 范围最坏到 sum(weights)。

代入数据范围：n ≤ 5 × 10⁴，sum(weights) ≤ n × 500 = 2.5 × 10⁷，最坏 5 × 10⁴ × 2.5 × 10⁷ = 1.25 × 10¹²。LC 单测 1 秒上限是 10⁸ 量级——TLE 四个数量级，必须砍。

can_ship 本身就是 O(n)，没问题。卡脖子的是外层"一个一个 cap 试"——这一步能不能换成二分？

can_ship 关于 cap 单调

你看 can_ship 这个函数的性质：

如果 cap = c 能在 days 天内运完，那么 cap = c + 1 也一定能在 days 天内运完。

直觉很简单：船更大只会更轻松。严格证明也不难——用更大的 cap 重新跑一次 can_ship，每一天能装的包裹只会更多不会更少，所以总天数只减不增。

这意味着 can_ship(cap) 关于 cap 是单调函数：从左到右一片 False，然后翻成一片 True，中间夹着一条边界。这条边界就是答案——第一个让 can_ship 变 True 的 cap。

下面的演示走一遍 LC 1011 例子 weights = [1,2,3,4,5,6,7,8,9,10], days = 5 在 cap 值域 [10, 11, ..., 17] 上的判定结果（红 = 装不下、绿 = 装得下、金 = 当前二分到的值）：

整段值域被切成"红色不可行 + 蓝色可行"两片，二分就是在找这条 False → True 的翻转边界。

说白了，边界 = lower_bound。直接套上一章的模板，唯一变的是二分对象从数组下标搬到了 cap 的值域。复杂度变成 O(n log V)——V 是值域 sum(w) − max(w) ≈ 2.5 × 10⁷，log V ≈ 25，总操作 5 × 10⁴ × 25 = 1.25 × 10⁶，秒过。

下面把这件事抽象成一类问题的通解。

4. 五道例题：判定函数怎么造

4.1 LC 1011 在 D 天内送达包裹的能力

链接：LeetCode 1011

题意：传送带上有 n 个包裹，第 i 个重 weights[i]。船一天能装总重不超过载重 cap 的若干个包裹，且包裹要按数组顺序装。给天数 days，返回能在 days 天内运完的最小载重。

数据范围：n 1 到 5 × 10⁴，weights[i] 1 到 500，days 1 到 n。

示例：

输入：weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
输出：15

回到本章开头那道题。check(cap) 用贪心扫一遍：从左到右累加，超过 cap 就开新一天，最后看天数是否 ≤ days。

值域怎么定？[max(weights), sum(weights)]——下界 max(weights)（不然单个包裹都装不下），上界 sum(weights)（最坏一天全装完）。这两个边界是这题的"基石"，记牢这个套路：最小可行答案 ≤ 真实答案 ≤ 最大可行答案。

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(cap: int) -> bool:
            d, cur = 1, 0
            for w in weights:
                if cur + w > cap:
                    d += 1
                    cur = w
                else:
                    cur += w
            return d <= days

        lo, hi = max(weights), sum(weights) + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if can_ship(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = Math.max(lo, w);
            hi += w;
        }
        hi += 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    private boolean canShip(int[] weights, int days, int cap) {
        int d = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { d++; cur = w; }
            else cur += w;
        }
        return d <= days;
    }
}

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = max(lo, w);
            hi += w;
        }
        hi += 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

private:
    bool canShip(vector<int>& weights, int days, int cap) {
        int d = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { d++; cur = w; }
            else cur += w;
        }
        return d <= days;
    }
};

复杂度 O(n log V)，V = sum(w) ≤ 2.5 × 10⁷，log V ≈ 25，总操作约 10⁶。空间 O(1)。

Follow-up：上面是"按数组顺序连续切"。如果把数组切成 k 段、让最大段和最小，是不是同一个套路？

4.2 LC 410 分割数组的最大值

链接：LeetCode 410

题意：给一个正整数数组 nums 和整数 k。把 nums 按顺序切成 k 个非空连续子数组。每种切法对应的"最大子数组和"是 k 段中和最大的那一段。返回所有切法里最小的那个"最大子数组和"。

数据范围：

• nums.length：1 到 1000
• nums[i]：0 到 10⁶
• k：1 到 min(50, nums.length)

示例：

输入：nums = [7, 2, 5, 10, 8], k = 2
输出：18
解释：切成 [7, 2, 5] 和 [10, 8]，两段和 14 和 18，最大 18。其他切法的最大值都 ≥ 18。

说白了，跟 LC 1011 是同一个判定函数，只是换了变量名：

• LC 1011：固定 days，找最小的 cap（载重就是"段和上界"）。
• LC 410：固定 k 段，找最小的"段和上界"。

check(threshold) 完全是 LC 1011 的 can_ship——贪心累加，超过 threshold 就开新一段，最后看段数 ≤ k。

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def check(threshold: int) -> bool:
            segs, cur = 1, 0
            for x in nums:
                if cur + x > threshold:
                    segs += 1
                    cur = x
                else:
                    cur += x
            return segs <= k

        lo, hi = max(nums), sum(nums) + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if check(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0;
        long hi = 1;                       // sum(nums) + 1，用 long 防溢出
        for (int x : nums) {
            if (x > lo) lo = x;
            hi += x;
        }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2; // 也用 long，与 sum 兼容
            if (check(nums, k, mid)) hi = mid;
            else lo = (int) (mid + 1);
        }
        return lo;
    }

    private boolean check(int[] nums, int k, long threshold) {
        int segs = 1;
        long cur = 0;
        for (int x : nums) {
            if (cur + x > threshold) {
                segs++;
                cur = x;
            } else {
                cur += x;
            }
        }
        return segs <= k;
    }
}

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int lo = 0;
        long long hi = 1;                       // sum(nums) + 1，用 long long 防溢出
        for (int x : nums) {
            if (x > lo) lo = x;
            hi += x;
        }
        while (lo < hi) {
            long long mid = lo + (hi - lo) / 2; // 也用 long long，与 sum 兼容
            if (check(nums, k, mid)) hi = mid;
            else lo = (int)(mid + 1);
        }
        return lo;
    }

private:
    bool check(vector<int>& nums, int k, long long threshold) {
        int segs = 1;
        long long cur = 0;
        for (int x : nums) {
            if (cur + x > threshold) {
                segs++;
                cur = x;
            } else {
                cur += x;
            }
        }
        return segs <= k;
    }
};

注意 Java 的 long：sum(nums) 上界可达 1000 × 10⁶ = 10⁹，刚好在 int 边界内。但加上 + 1 后 mid 的中间运算用 long 更稳妥；老题用 int 也能过，但养成"求和先看溢出"的习惯能在 LC 410 这种边界题上少踩坑。

复杂度 O(n log V)，与 LC 1011 同构。这两题代码几乎一模一样，只是变量名换了——同一个 check 函数换层皮，认出来后两题写法基本一致。

Follow-up：上面两题都是"最小化最大值"。方向反过来——最大化最小值——还能用同一套模板吗？

4.3 LC 2517 礼盒的最大甜蜜度

链接：LeetCode 2517

题意：给一个数组 price 和整数 k，从中选 k 个糖，定义"甜蜜度"为所选糖中任意两个的价格差的最小值。返回最大可能的甜蜜度。

数据范围：

• price.length：2 到 10⁵
• price[i]：1 到 10⁹
• k：2 到 price.length

示例：

输入：price = [13, 5, 1, 8, 21, 2], k = 3
输出：8
解释：选 {1, 13, 21}，两两差是 12, 8, 20，最小 8。

方向反过来了——这次是最大化最小值。模板需要小调整：找最大的 d 使 check(d) = True，等价于"找最大的 d 使能选 ≥ k 个间距 ≥ d 的糖"。

check(d) 怎么造？先把 price 排序，然后贪心选——每次只要当前糖跟上一个选中的糖差 ≥ d 就选。能选到 ≥ k 个就返回 True。本质上是：要让最小间距尽量大，就尽量"挑得稀疏"，贪心一遍最稳。

class Solution:
    def maximumTastiness(self, price: list[int], k: int) -> int:
        price.sort()

        def check(d: int) -> bool:
            """能否在 price 中选出 k 个，使两两差 >= d？"""
            cnt, last = 1, price[0]
            for x in price[1:]:
                if x - last >= d:
                    cnt += 1
                    last = x
                    if cnt >= k:
                        return True
            return cnt >= k

        lo, hi = 0, (price[-1] - price[0]) // (k - 1) + 1
        # 注意：上界 (max - min) / (k - 1) 是间距能达到的最大值
        while lo < hi:
            mid = (lo + hi + 1) // 2          # 上取整！
            if check(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

最大化方向跟最小化是镜像对称的，模板要改三处：

1. lo = mid（保留 mid 作为候选下界），hi = mid - 1。
2. mid = (lo + hi + 1) // 2——上取整，避免 lo, hi = x, x+1 时 mid = lo 死循环。
3. 终止条件 lo == hi，返回 lo。

跟"最小化"方向（LC 1011/410）正好对调。口诀：找最小用下取整 + hi = mid，找最大用上取整 + lo = mid。

上界 (price[-1] - price[0]) // (k - 1) 是个有用的剪枝：把 price 均分成 k - 1 段，每段长度就是"平均间距"——最大间距不可能超过这个均值（鸽巢原理）。+ 1 是因为模板左闭右开。

复杂度 O(n log n + n log V)，V = 10⁹，log V ≈ 30，主导项 O(n log V) ≈ 3 × 10⁶。

Follow-up：上面三题的判定函数都是"贪心扫一遍"。如果判定函数是个数学公式呢？

4.4 LC 1760 袋子里最少数目的球

链接：LeetCode 1760

题意：给一个数组 nums 表示 n 个袋子里的球数（nums[i] 个）。每次操作可以把一个袋子里的球分成两堆放回（拆成两个袋子）。最多操作 maxOperations 次。返回操作后单个袋子里球数的最大值的最小值。

数据范围：

• nums.length：1 到 10⁵
• nums[i]：1 到 10⁹
• maxOperations：1 到 10⁹

示例：

输入：nums = [9], maxOperations = 2
输出：3
解释：[9] → [6, 3] → [3, 3, 3]。两次操作把单袋最大球数降到 3。

输入：nums = [2, 4, 8, 2], maxOperations = 4
输出：2

最小化最大值——check(limit) 就是"能不能在 maxOperations 次内让所有袋子 ≤ limit"。

每个袋子 nums[i] 独立看：

• 如果 nums[i] <= limit：0 次操作，跳过。
• 否则要拆成若干袋，每袋 ≤ limit。操作次数 = ⌈nums[i] / limit⌉ − 1（把 nums[i] 个球均分到 ⌈nums[i] / limit⌉ 个袋子里，每次操作多一个袋子，所以操作次数 = 袋子数 − 1）。

这就是"数学公式型"判定函数——每个元素独立用公式算贡献，求和判定。比贪心扫一遍还干净。

class Solution:
    def minimumSize(self, nums: list[int], maxOperations: int) -> int:
        def check(limit: int) -> bool:
            ops = 0
            for x in nums:
                ops += (x + limit - 1) // limit - 1   # ⌈x / limit⌉ − 1
                if ops > maxOperations:
                    return False
            return True

        lo, hi = 1, max(nums) + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if check(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

复杂度 O(n log V)，V = 10⁹，约 3 × 10⁶ 操作。

(x + limit - 1) // limit 是整数版上取整 ⌈x / limit⌉——比 math.ceil 快、不引入浮点。Java / Go / C++ 也是这个写法。Python 还可以写 -(-x // limit)，更短。

这道题判定函数是 O(n) 的，但没有外层贪心串——每个袋子独立用数学公式算操作数，求和即可。这种"独立累加"的判定函数比扫一遍贪心还直接。

Follow-up：上面四道题都是整数二分。要是答案本身是个浮点数呢？

4.5 LC 644 子数组最大平均数 II

链接：LeetCode 644

题意：给一个数组 nums 和整数 k。找一个长度 ≥ k 的连续子数组，使它的平均值最大。返回这个最大平均值。允许 10⁻⁵ 的精度误差。

数据范围：

• nums.length：1 到 10⁴
• nums[i]：−10⁴ 到 10⁴
• k：1 到 nums.length

示例：

输入：nums = [1, 12, -5, -6, 50, 3], k = 4
输出：12.75
解释：长度 5 的子数组 [12, -5, -6, 50, 3]，平均 (12 - 5 - 6 + 50 + 3) / 5 = 10.8。
但长度 4 的 [12, -5, -6, 50]，平均 51 / 4 = 12.75，更大。

这题要二分实数答案 avg。判定函数 check(avg) = "是否存在长度 ≥ k 的子数组平均值 ≥ avg"。

关键的转化在这里：长度 L 的子数组平均值 ≥ avg 等价于 sum(nums[i..i+L]) / L >= avg，等价于 sum(nums[i..i+L]) - L * avg >= 0，等价于把数组每个元素减去 avg 后求子数组和 ≥ 0。一个除法变成一个减法，平均值问题被翻译成熟悉的"子数组和"问题。

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        def check(avg: float) -> bool:
            """是否存在长度 >= k 的子数组，元素全减 avg 后和 >= 0"""
            # 令 b[i] = nums[i] - avg，要找某个长度 >= k 的子数组 b[l..r] 和 >= 0
            # 维护 cur = b[0..r] 的前缀和（含右端 r），prev_sum = b[0..l-1] 的前缀和（l-1 = r-k 的最远左端起点）
            cur = sum(nums[i] - avg for i in range(k))   # 先填 b[0..k-1]，对应 r=k-1
            if cur >= 0:
                return True
            prev_sum, min_prev = 0.0, 0.0                # min_prev = min(0, prev_sum 历史)
            for i in range(k, len(nums)):
                cur += nums[i] - avg                     # 现在 cur = b[0..i]，r = i
                prev_sum += nums[i - k] - avg            # prev_sum = b[0..i-k]，是允许的最远左端 + 1
                if prev_sum < min_prev:
                    min_prev = prev_sum
                # cur - min_prev = 右端固定为 i、长度 >= k 的最大子数组和
                if cur - min_prev >= 0:
                    return True
            return False

        lo, hi = min(nums), max(nums)
        for _ in range(100):                        # 浮点二分固定 100 次
            mid = (lo + hi) / 2
            if check(mid):
                lo = mid
            else:
                hi = mid
        return lo

复杂度 O(100 n) ≈ 10⁶，跑得很快。

这道题有三个值得拎出来的技巧：

一是 减偏移转化——(sum / L >= avg) ⇔ (sum − L · avg >= 0)。这一步把"平均值"这个除法消掉，变成"减偏移后子数组和"这个熟悉的线性问题。这种"消除非线性"的转化在二分答案里反复出现。

二是 长度 ≥ k 的最大子数组和——维护当前长度恰好 k 的窗口和 cur，再维护"k 个之前位置的最小前缀和" min_prev。cur - min_prev 就是右端固定为当前位置、长度 ≥ k 的最大子数组和。Kadane 算法的加长版。

三是 浮点二分固定 100 次——不要用 while hi - lo > 1e-5，浮点累计误差可能不收敛。100 次迭代 = 2¹⁰⁰ 倍精度收缩，远超 IEEE 754 双精度尾数 52 位的需求；浮点二分常用固定迭代次数避开收敛问题。

5. 边界、易错与复杂度

判定函数的常见七类

二分答案的核心在 check 的实现。把这五道题（外加大厂作业）的判定函数套路汇总成表，覆盖大多数二分答案题的 check 形态，可作为模式匹配参照：

值域上下界（必须包住真实答案）

下界 lo 取"理论最小可行答案"，上界 hi 取"理论最大可行答案"。给错任意一边二分直接废。

• LC 1011 / 410：lo = max(weights)（单个元素必须装得下）、hi = sum(weights)（最坏一天装完）。
• LC 2517：lo = 0（间距至少 0）、hi = (max - min) / (k - 1)（鸽巢上界）。
• LC 1760：lo = 1（每袋至少 1 球）、hi = max(nums)（不操作就是上界）。

整数二分用左闭右开 [lo, hi)、hi 取上界 + 1。浮点二分用闭区间 [lo, hi]（浮点没有 +1 这种说法）。

浮点二分要兜底 100 次

实数版（LC 644 / LC 786 / LC 1631 浮点版）必须用固定迭代次数，不要写 while hi - lo > eps——浮点累计误差可能让它永不收敛。100 次迭代覆盖 2¹⁰⁰ 倍精度收缩，远超双精度 52 位尾数的需求。

单调性"伪证"陷阱

写判定函数前要先严格验证它是单调的。容易出问题的是凭直觉判，实际却不单调：

• "排序后选 k 个最大数让某统计量最大"——可能不单调（换个顺序可能更大）。
• "动态规划状态里嵌一个阈值"——阈值不一定单调影响 DP 值。

证明单调性的两种常见办法：

• 包含证明：x 可行的方案在 x + 1 下也可行。
• 构造证明：从 x + 1 的方案能构造出 x 的方案。

写题前先把单调性证一下，套模板前没证清楚容易翻车。

最大化方向的模板镜像

LC 2517 是最大化方向，模板有三处差异——lo = mid、hi = mid - 1、mid = (lo + hi + 1) // 2（上取整）。最小化和最大化两套都要熟。

口诀同前：找最小用下取整 + hi = mid；找最大用上取整 + lo = mid。

整数 / 浮点 / 大整数对比

Python 整数无溢出，跨语言移植大整数题时要小心 Java / Go / C++ 的 long 上界。LC 410 的 sum(nums) 在 nums[i] <= 10⁶, n <= 1000 时是 10⁹，仍在 int32 内；但放大到 n = 10⁵ 就要 long。

复杂度速查

7. 小结

二分答案的核心就一句话：写一个关于候选答案 x 单调的 check(x)，然后套 lower_bound。判定函数是工作量大头，模板是死的。

回头看，本章框架同上一章——搜索区间 [lo, hi) + while lo < hi + 看判定函数。换的只是判定函数的"语义"：从下标比较换成了"x 可不可行"。

下一章 第 K 小（在值域上二分） 把这套思路再推一步——二分对象从"答案值"再换成"统计量"，给候选 x 数一下 count_leq(x)，再二分 x。骨架完全不变，判定函数再换一次面孔。

对应灵神题单：二分答案 / 最大化最小值 / 最小化最大值

进一步阅读：灵茶山艾府《二分算法题单》第二部分；LeetCode 二分答案标签