Binary Search on Answer
The Core Idea
Instead of searching within a sorted array, you’re searching over the range of possible answers to an optimization or feasibility problem. You assume there’s a monotonic predicate $P(x)$ on that range:
- For all $x < A, P(x)$ is false
- For all $x \geq A, P(x)$ is true
Your goal is to find the smallest (or largest) $A$ for which $P(A)$ flips to true.
When to Use It
- Optimization problems where you want the minimum/maximum parameter satisfying some constraint.
- You can quickly check feasibility for a candidate answer in, say, $O(f(n))$.
- The predicate is monotonic (once true, stays true as you move right).
Pseudocode
Initialize your search bounds:
$L := $ lowest possible answer
$R := $ highest possible answer
Loop while L < R:
$mid := L + (R - L) / 2$
if $P(mid)$ is true:
$R := mid$ // answer is ≤ mid
else:
$L := mid + 1$ // answer is > mid
Return R (or L) as the optimal answer:
Find smallest $x$ in $[L..R]$ with $P(x)==true$
int bs_on_answer(int $L$, int $R$):
while $L < R$:
int $mid = L + (R - L) / 2$
if $P(mid)$ is true:
$R := mid$
else:
$L := mid + 1$
return $R$
It may also look like:
int bs_on_answer(int $L$, int $R$):
$L := L - 1$
$R := R - 1$
while $R - L > 1$:
int $mid = L + (R - L) / 2$
if $P(mid)$ is true:
$R := mid$
else:
$L := mid$
return $R$
Last updated 11 May 2025, 18:45 +0500 .