本文讲解如何通过二分搜索优化“办公室饼干”问题的求解，替代线性搜索，将时间复杂度从 o(n·k) 降至 o(n·log(maxc))，并修正原实现中边界处理、零值过滤、初始范围设定等关键错误。
本文讲解如何通过二分搜索优化“办公室饼干”问题的求解，替代线性搜索，将时间复杂度从 o(n·k) 降至 o(n·log(maxc))，并修正原实现中边界处理、零值过滤、初始范围设定等关键错误。
在“办公室饼干”问题中，开发者 Fyodor 需在 M 小时内吃完 N 个地点共 sum(Cₙ) 块饼干。每小时他只能访问一个地点，且必须吃掉恰好 K 块（若剩余不足 K 块，仍耗时 1 小时）。目标是求满足条件的最小整数 K。
原方案采用线性搜索 + 排序预处理，但存在多个致命缺陷：
- ❌ 零值过滤逻辑错误：sort.slice(sort.findIndex(e => e > 0)) 在全为 0 时 findIndex 返回 -1，导致 slice(-1) 取出错误子数组；更严重的是，placesCount（输入的 N）包含零值位置，但实际可访问地点数应为 Cₙ > 0 的数量（记为 nonZeroCount），而原代码错误地用 placesCount 判断 N > M，忽略了零值不占时间。
- ❌ 下界初始化不合理：minCookie = totalCookies
- ❌ 未校验最大候选 K 是否可行：若 maxCookie = max(Cₙ) 对应的耗时 ∑⌈Cₙ / maxCookie⌉ > M，说明无解，应返回 0。原代码直接假设 maxCookie 可行，跳过验证。
- ❌ 边界场景遗漏：当 totalCookies === 0 时应直接返回 0；当 nonZeroCount > M（即非零地点数超过总小时数），因每地至少耗 1 小时，必然无法覆盖所有非零地点 → 返回 0。
✅ 正确解法是二分搜索 K，核心在于：
-
确定搜索范围：
- left = 1（K 至少为 1，除非无饼干）；
- right = Math.max(...nonZeroList)（K 不必超过单堆最大值，否则该堆仍只需 1 小时）；
- 特殊情况：若 totalCookies === 0，直接返回 0；若 nonZeroCount > M，返回 0。
-
检查函数 isHighEnough(k)：
const isHighEnough = (k) => { let hoursNeeded = 0; for (const c of nonZeroList) { hoursNeeded += Math.ceil(c / k); if (hoursNeeded > M) return false; // 提前剪枝，防溢出 } return hoursNeeded <= M; }; -
标准二分模板（求最小可行 K）：
let left = 1, right = maxNonZero; // 先验证 right 是否可行，不可行则无解 if (!isHighEnough(right)) return 0; while (left < right) { const mid = Math.floor(left + (right - left) / 2); if (isHighEnough(mid)) { right = mid; // mid 可行，尝试更小 } else { left = mid + 1; // mid 不可行，必须增大 } } return left;
? 完整修复后的关键步骤示例：
// 输入解析后，构建非零列表
const nonZeroList = list.filter(c => c > 0);
const nonZeroCount = nonZeroList.length;
const totalCookies = nonZeroList.reduce((a, b) => a + b, 0);
if (totalCookies === 0) return 0;
if (nonZeroCount > M) return 0; // 每堆至少 1 小时，不够用
const maxNonZero = Math.max(...nonZeroList);
// 验证上界是否可行
if (!isHighEnough(maxNonZero)) return 0;
// 二分搜索
let left = 1, right = maxNonZero;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (isHighEnough(mid)) right = mid;
else left = mid + 1;
}
return left;⚠️ 注意事项：
- 使用 Math.ceil(c / k) 计算单堆耗时，避免浮点误差，不可用 Math.floor((c-1)/k) + 1 替代（当 c=0 时出错，但已过滤零值）；
- 提前剪枝 if (hoursNeeded > M) 显著提升最坏情况性能；
- left 初始为 1 而非 Math.ceil(totalCookies/M)，因后者在 M 很大时可能为 0，而 K 必须 ≥1；
- 所有整数运算，无需考虑浮点精度问题。
该方案时间复杂度为 O(N·log(maxC))，空间复杂度 O(N)，完全满足题目 10⁵ 数据规模与 64MB 内存限制。
