how can we identify that a problem can be solved using binary search
Some problems with binary search will contain the phrases “find the maximum value such that…” “find the minimum value such that…” “find the kth…”
6 Likes
just check the monotonicity of the function you are working with.
Meaning if the function is f(x) then if one of the condition should be satisfied ( Actually both are same but whichever you can understand easily).
1. x1 \le x2 implies f(x1) \le f(x2)
2. if f(x1) = k implies f(x2) \ge k when x2 \ge x1 ?
Then you can use binary search.
You will find many questions where you will do “Binary Search over answer”
You just have to see if a value k satisfies given conditions then will all values \ge k satisfy those conditions and if value k doesn’t satisfy given conditions then will all values \le k not satisfy it ?
Or vice-versa.
Note that you might have to tweak given conditions of question sometimes so that it becomes monotonic.
4 Likes