Binary Answer

What's Binary Answer

When the search range is small, the binary answer problems are solvable by linear scaning the answer range. For example, assume the answer range is [0, 100], we can check 0, then 1, ..., then 100, and we return the maximum number that is valid.

However, when the answer range is large, say [0, 10^5], linear scanning the entire answer range will get TLE.

So, instead of doing O(N) linear scanning, we binary search in the answer range which reduces the time complexity to O(logN).

When can we use Binary Answer?

We can use "Binary Answer" solution if we can write a predicate function valid(i) that has monotocity:

  • If valid(i) == true, then valid(j) == true for all j <= i.

  • If valid(i) == false, then valid(j) == false for all j >= i.

Algorithm

Our goal is the find the maximum i that valid(i) == true.

We can use two pointers L = minVal, R = maxVal, and keep using binary search to move the pointers towards each other until they swap order. In the end, R will point to the largest value that is valid, L will point to the smallest value that is invalid.

Pseudo Code

Assume the answer range is monotonically going from valid to invalid, and we are looking for the maximum valid value.

int L = minVal, R = maxVal
while (L <= R) {
    int M = (L + R) / 2;
    if (valid(M)) L = M + 1;
    else R = M - 1;
}
return R >= minVal ? R : NOT_FOUND;

If we are looking for the minimal invalid value, simply return L <= maxVal ? L : NOT_FOUND.

Problems

PreviousBacktrackingNextBinary Lifting

Last updated