Binary Search on the Answer
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Some problems have no sorted list at all. The answer is a number, such as a capacity or a speed, and a check tells whether a number is big enough. Binary search can search the numbers themselves.
Search the answer, not the list
A monotonic check is a yes or no test that is no up to some value and yes from there on (or the reverse). Binary search on the answer finds the point where it flips.
Pick a number in a known range and ask a yes or no question about it. If the answer is no for small numbers and yes for every larger one, binary search finds the first yes.
Example 1 · Brute force: try capacities one by one
def days_needed(weights, capacity): used, load = 1, 0 for weight in weights: if load + weight > capacity: used += 1 load = 0 load += weight return used
weights = [4, 8, 3, 9, 5, 2]days = 3capacity = max(weights)while days_needed(weights, capacity) > days: capacity += 1print(capacity)12
What this code does
- Packages must ship in order, in at most 3 days. A truck cannot be smaller than the heaviest package, so the search starts there.
- Each try costs O(n) and there can be up to sum(weights) tries, which is slow for large inputs.
The first-true template
Write the check as a function ok(x). Search lo..hi for the first x where ok(x) is true. If ok(mid) is true, mid might be the answer, so keep it with hi = mid. If false, lo = mid + 1.
def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo
print(first_true(0, 100, lambda x: x * x >= 50))8
Example 2 · Better: binary search the capacity
def days_needed(weights, capacity): used, load = 1, 0 for weight in weights: if load + weight > capacity: used += 1 load = 0 load += weight return used
def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo
weights = [4, 8, 3, 9, 5, 2]days = 3answer = first_true(max(weights), sum(weights), lambda cap: days_needed(weights, cap) <= days)print(answer)12
What this code does
- The check "ships in at most 3 days" is no for small capacities and yes for large ones. The window starts at max(weights) and ends at sum(weights), which always works in one day.
- Cost is O(n log(sum)): the check runs about log(sum) times. The answer matches the brute force.
The value at hi must satisfy the check, so an answer always exists inside the window. When lo meets hi, that number is the first yes.
Koko-style speed
An agent clears piles of tickets, one pile at a time, at a speed of s tickets per hour. A pile of 11 at speed 4 takes 3 hours. Find the lowest speed that finishes all piles within h hours.
def hours_needed(piles, speed): return sum((pile + speed - 1) // speed for pile in piles)
print(hours_needed([3, 6, 7, 11], 4))print(hours_needed([3, 6, 7, 11], 3))8 10
Example 3 · Smallest eating speed
def hours_needed(piles, speed): return sum((pile + speed - 1) // speed for pile in piles)
def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo
piles = [30, 11, 23, 4, 20]for hours in [5, 6]: print(hours, "hours ->", first_true(1, max(piles), lambda speed: hours_needed(piles, speed) <= hours))5 hours -> 30 6 hours -> 23
What this code does
- With 5 hours there is one hour per pile, so the speed must clear the biggest pile in one hour: 30. With 6 hours one pile can take two hours.
- Speed max(piles) always fits, so it is a safe upper bound.
A higher speed never needs more hours, so the check "fits in h hours" is monotonic. (pile + speed - 1) // speed rounds up using whole numbers only, so it is exact for any size.
Integer square root and choosing bounds
The integer square root of n is the largest x with x * x <= n. Find the first x whose square is above n, then subtract one. Start with lo = 0 and hi = n + 1.
def int_sqrt(n): lo, hi = 0, n + 1 while lo < hi: mid = (lo + hi) // 2 if mid * mid > n: hi = mid else: lo = mid + 1 return lo - 1
print(int_sqrt(50))print(int_sqrt(49))7 7
Example 4 · Integer square root checked against math.isqrt
import math
def int_sqrt(n): lo, hi = 0, n + 1 while lo < hi: mid = (lo + hi) // 2 if mid * mid > n: hi = mid else: lo = mid + 1 return lo - 1
for n in [0, 1, 15, 16, 10**12, 10**18]: print(n, int_sqrt(n), math.isqrt(n))0 0 0 1 1 1 15 3 3 16 4 4 1000000000000 1000000 1000000 1000000000000000000 1000000000 1000000000
What this code does
- Both columns agree, including for 10**18, where a float square root would be unsafe.
- About 60 steps are enough for 10**18. In real code use math.isqrt, and in an interview write the search.
Example 5 · Last true needs the upper middle
def last_true(lo, hi, ok): while lo < hi: mid = (lo + hi + 1) // 2 if ok(mid): lo = mid else: hi = mid - 1 return lo
print(last_true(0, 1000, lambda x: x * x <= 1000))31
What this code does
- This time the check is yes for small values and no for large ones, so we want the last yes. When ok(mid) is true we keep mid with lo = mid.
- The middle is rounded up with + 1. With a lower middle, lo = mid would not move when mid equals lo, and the loop would never end.
Choose lo as the smallest value that could be the answer and hi as a value that surely passes. Tight bounds save a few steps, but correct bounds matter far more.
Next step
Check your understanding
11 quick questions