How does binary search on the answer work?

Category: DSA Patterns

Answer

When the question is “is X possible?” and X is monotonic (more X always works, less X doesn’t), you can binary search the answer. Check the predicate in O(N) and walk the search space in O(log RANGE).

Concrete examples from the fca project context

Example 1

Min max subarray sum <= K: binary search K; check predicate by greedy split.

Example 2

Min days to ship: binary search days; check “can produce N units per day”.

Example 3

Capacity to ship packages within D days: binary search the per-day capacity.

Data flow / flow chart

lo .. hi
  mid = (lo+hi)/2
  can_achieve(mid)?
  if yes: hi = mid
  if no:  lo = mid + 1

Takeaway

When the predicate is monotonic, binary-search the answer; O(log range) beats O(N^2).