Binary Search on Answer
Searching: lesson 5 of 8
No sorted array? Binary search the answer range.
Lesson 5 of 8 · 6 min
Binary Search on Answer
Step 1 of 9
weights3 2 2 4 1 4trips ≤3
mid
4
5
6
7
8
9
10
11
12
13
14
15
lo
hi
No array to search — instead search the answers: every van capacity from 4 to 15.
The Idea
Some problems hand you no array to search, but their answers still have order: if a value works, every larger value works too. Binary search that range of candidate answers, using a feasibility check in place of a comparison.
Real-World Example
Picking the smallest delivery van that clears the day's orders in the allowed number of trips. You do not measure every van, you try a mid-size one, see whether it fits, and halve the catalogue from there.
The Code
def min_capacity(weights, trips):
def fits(cap):
used, load = 1, 0
for w in weights:
if load + w > cap: # start a new trip
used, load = used + 1, 0
load += w
return used <= trips
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if fits(mid): hi = mid # try something smaller
else: lo = mid + 1
return lo
# min_capacity([3, 2, 2, 4, 1, 4], 3) -> 6Your turn
Fill in the blank.
lo, hi = 1, 100
while lo < hi:
mid = (lo + hi) // 2
# mid works, so nothing larger is needed
if fits(mid):
hi = ___
else:
lo = mid + 1Mini quiz
1 / 3