Binary Search on Answer

When a yes/no condition on a candidate answer is monotonic (true for all values above some threshold, false below), binary search directly over the ANSWER space rather than the input — turning many 'find the optimal X' problems into O(log(range)) checks.

Category

Algorithmic Techniques

Time complexity

O(n log(max))

Space complexity

O(1)

Pseudocode

lo, hi ← smallest, largest possible answer
while lo < hi:
  mid ← (lo+hi)/2; if feasible(mid): hi=mid else lo=mid+1
answer = lo

Reference implementation

lo, hi = 1, max(piles)
while lo < hi:
    mid = (lo + hi) // 2
    if can_finish(mid): hi = mid
    else: lo = mid + 1
return lo

Open the interactive Binary Search on Answer visualisation →