Koko Eating Bananas：二分查找中常见的逻辑与精度陷阱解析-java教程-PHP中文网

Koko Eating Bananas：二分查找中常见的逻辑与精度陷阱解析

本文深入剖析leetcode 875题“koko eating bananas”的典型错误——核心在于误算每堆香蕉所需小时数，以及二分边界更新后返回值处理不当，导致算法无法正确收敛到最小合法速度。

本文深入剖析leetcode 875题“koko eating bananas”的典型错误——核心在于误算每堆香蕉所需小时数，以及二分边界更新后返回值处理不当，导致算法无法正确收敛到最小合法速度。

在解决“Koko Eating Bananas”问题时，目标是找到最小整数吃速 k，使得Koko能在 h 小时内吃完所有香蕉。直觉上容易想到用二分查找在 [1, max(piles)] 范围内搜索答案——这本身思路正确，但实现细节极易出错。

? 关键错误一：错误的耗时计算逻辑

你的 canEatPiles 方法将总香蕉数除以速度并向上取整：

int hours = (int) Math.ceil((double) sum / capacityPerHour);

这是根本性误解。题目明确要求：

每小时只能选一堆，吃掉最多 k 根；若该堆不足 k 根，则本小时吃完这堆，且不再吃其他堆。

这意味着耗时不是 total / k，而是对每一堆独立计算所需小时数，再求和：

堆大小为 x、速度为 k → 需要 ⌈x / k⌉ 小时（即 (x + k - 1) / k 整数除法）
总耗时 = Σ ⌈piles[i] / k⌉

✅ 正确实现如下：

private int hoursNeeded(int k, int[] piles) {
    int totalHours = 0;
    for (int pile : piles) {
        totalHours += (pile + k - 1) / k; // 等价于 Math.ceil(pile / (double)k)
    }
    return totalHours;
}

❌ 错误示例验证：piles = [3,6,7,11], k = 4

错误算法：(3+6+7+11)=27 → ⌈27/4⌉ = 7 ❌（实际需 8 小时）
正确计算：⌈3/4⌉ + ⌈6/4⌉ + ⌈7/4⌉ + ⌈11/4⌉ = 1 + 2 + 2 + 3 = 8 ✅

? 关键错误二：二分返回值逻辑错误

你的循环结束后直接返回 mid，但 mid 是最后一次计算的中间值，不保证是满足条件的最小 k。二分搜索的目标是找到最左侧满足 hoursNeeded(k) ≤ h 的 k，应返回 l（左边界），而非 mid。

此外，推荐使用更安全的中点计算避免整数溢出：

int mid = left + (right - left) / 2;

✅ 完整修正代码

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = Arrays.stream(piles).max().orElse(1);

        while (left <h3>⚠️ 注意事项总结</h3>