Binary Search on Answer
Binary search on answer is a technique used when we need to find a value that satisfies a condition, and the answer space is monotonic (e.g., find minimum x such that f(x) is true). Instead of searching on the array, we search on the answer range.
Common problems: find the square root of a number, find the smallest capacity to ship packages, etc.
Example: find square root of a number using binary search.
public static int sqrt(int x) {
if (x < 2) return x;
int left = 2, right = x / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
long square = (long) mid * mid;
if (square == x) return mid;
if (square < x) left = mid + 1;
else right = mid - 1;
}
return right;
}
The key is to define a predicate that is monotonic, then binary search over the range of possible answers.
Two Minute Drill
- Binary search on answer applies when the answer space is monotonic.
- Define a condition f(mid) that is true for all values >= some threshold.
- Use binary search to find the boundary.
- Common in optimization problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com