Module 4 · Graphs, greedy and interview polish Lesson 14 of 15
Binary search on the answer
When the answer is a number and "is X good enough" is easy to check, binary search the answer instead of trying every value. It turns a linear scan into a logarithm.
The concept
The hard part is the check, not the search. Write a plain function that answers yes or no for one value; the binary search around it is five lines.
Off-by-one is the classic bug - decide once whether the answer is the low or the high end, and keep that convention through the loop.
def ship_within(capacity, weights, days):
used, current = 1, 0
for w in weights:
if current + w > capacity:
used += 1
current = 0
current += w
return used <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if ship_within(mid, weights, days):
hi = mid
else:
lo = mid + 1
print(lo)Worked example
"Smallest ship capacity to move all packages in D days" is checked by a simple simulation at each candidate capacity, then binary-searched.
Your practice task
Solve "minimum capacity to ship in D days" and write the check function separately from the search.
Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.
Key takeaway
The hard part is the check, not the search.
Keep your place in this course
A free account saves which lessons you have finished and unlocks the certificate. The lesson itself stays free to read.
Create free account or sign inCourse complete
You finished every lesson.
Your certificate is ready, and the projects you built are the proof to attach to an application.
Almost there
15 lessons left of 15
Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.