Space
Open
From Fieldwork
Scales
Archive
Used for: Koko Eating Bananas, Minimize Max Distance to Gas Station, Capacity to Ship Packages.
Visual Logic: You aren't looking for a number in an array. You are guessing an answer k. If k works, could a smaller k work? If k doesn't work, we need a bigger k.
Key Detail: Use left < right and mid = (left + right) // 2.
def min_capacity(weights, days):
# 1. Define Search Space
# The answer is somewhere between max(weights) and sum(weights)
left, right = max(weights), sum(weights)
# 2. Feasibility Function
def can_ship(capacity):
# Logic to check if this specific capacity works
ships_needed = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
ships_needed += 1
current_load = 0
current_load += w
return ships_needed <= days
# 3. Binary Search Template
while left < right:
mid = (left + right) // 2
if can_ship(mid):
# If it works, try to find a smaller/better answer
right = mid
else:
# If it fails, we strictly need more capacity
left = mid + 1
return leftPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode