Binary Answer
Last updated
Last updated
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).
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.
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.
Assume the answer range is monotonically going from valid to invalid, and we are looking for the maximum valid value.
If we are looking for the minimal invalid value, simply return L <= maxVal ? L : NOT_FOUND.
