Binary Search on Answer

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) -> 6

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 + 1