# Binary search identification

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