对答案进行二分查找
猜测结果并检查可行性
对答案进行二分查找 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
先猜测，再验证
有时您无法直接计算答案，但可以检查一个猜测。对答案进行二分查找，就能把困难的优化问题转化为简单的检查问题。
# guess X, ask: is X feasible?关键性质
当可行性具有单调性时，这种方法才有效：如果某个值可行，那么所有更大（或更小）的值也都可行。您要搜索的正是这种顺序。
# feasible(X) true => feasible(X+1) true确定答案范围
将可能答案中的最小值和最大值确定为low 和 high。对于最小容量问题，low 是一个物品的大小，high 是总和。
low, high = max(weights), sum(weights)编写可行性检查
该方法的核心是一个can(X) 函数：如果猜测值 X 可以实现，就返回真。它通常在线性时间内运行。
def can(cap):
# simulate and return True/False
...示例：在 D 天内运送
给定每日容量 cap，请用贪心方式填满每天的容量并统计天数。当天数不超过限制 D 时，can(cap) 为真。
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= D搜索最小容量
您要找的是能够通过检查的最小 cap。这是在容量范围内进行的首个为真查找，因此可以复用 high = mid 模板。
while low < high:
mid = (low + high) // 2保留可行的一半
如果 can(mid) 为真，更小的容量可能仍然可行，因此请设置 high = mid。否则使用 low = mid + 1 提高下限。
if can(mid):
high = mid
else:
low = mid + 1注意时间预算
总开销为O(检查次数 × 范围的对数)。在十亿宽度的范围上进行线性检查也只需约 30 次检查，足以应对严格的限制。
# log2(1e9) is about 30 iterations从最小化改为最大化
要找最大的可行值，请反转逻辑：搜索最后一个为真的位置。可行时提高 low，不可行时降低 high。
if can(mid):
low = mid
else:
high = mid - 1实数答案
对于浮点数答案，请固定循环次数，例如循环 100 次，而不是使用整数 mid。每轮都会将区间减半，很快就能达到极高精度。
for _ in range(100):
mid = (low + high) / 2识别这种模式
“最小的最大值”“最大的最小值”或“可行的最小 k”之类的表述，都是应当对答案进行二分查找的信号。请培养识别它们的敏锐度。
# 'minimize the maximum' => search answer快速检查
判断什么时候适合对答案使用二分查找。
回顾：搜索答案
现在您可以确定答案范围、编写可行性检查，并通过二分查找寻找最小值或最大值。困难的问题也能变成先猜测再验证。🏆
常见问题解答
「对答案进行二分查找」课时是免费的吗？
是的 — 「对答案进行二分查找」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「对答案进行二分查找」这节课中我会学到什么？
猜测结果并检查可行性 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「对答案进行二分查找」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。