How to Identify Binary Search Problems?

Based on the number of problems involving Binary Search, we can safely assume the scenario when Binary search is involved in a problem, as mentioned below:

Binary search can only be applied to a problem if and only if the Problem is monotonic in nature.

When a Problem is considered to be Monotonic?

Suppose we are given a problem f() and the expected solution to this problem is y, then we can define the problem as

y = f(n)

Now if this problem show a behaviour such that it either only increases or only decreases with the change in parameter. Then it is said that the problem shows Monotonic (only single direction) behaviour.

In other words, A function f(n1) is said to be monotonic if and only if:

• for any n1, if f(n1) returns true, then for any value of n2 (where n2 > n1), f(n2) should also return true,
• and similarly, if for a certain value of n1 for which f(n1) is false, then for any value n2 (n2 < n1) the function f(n2) should also return false.

The same is shown in the graph below:

Now if this problem shows a monotonic behavior, generally this tells you that you can apply a binary search here.

We all know that Binary search is the most efficient search algorithm as of now, and it has multiple applications in the programming domain for the same reason. But very often the problems do not have any information about applying Binary Search or even any hint on using a Searching algorithm altogether. So it becomes very important to have an understanding of how to identify Binary Search Problems, how to solve Binary Search problems and what are the most common interview questions that have a Binary Search solution involved. In this post, we have curated the topics to do just that.