Binary search by answer

Binary search by answer

Idea

Sometimes we are not looking for an element in an array, but for the smallest or largest answer that satisfies a condition.

The approach is:

• iterate over a possible answer mid;
• check: does it fit or not;
• if it fits — try to make the answer better;
• if it doesn't fit — keep searching.

Main condition

Monotonicity must hold:

• if mid fits, then all larger (or, in another formulation, all smaller) values also fit;
• if mid doesn't fit, then all smaller (or larger) also don't fit.

It is this property that makes it possible to apply binary search on the answer.

Template

Example problem

Given an integer $n$, it is required to find the minimum integer $x \geq n^2$.