Here is a short idea about binary search (BS) problem identification.

Suppose you reduce a problem (or parts of problem) to a function f(n) such that n € [Domain of f(n)] . Now **“If the change of f(n) is positive with the change of n” **then most likely we are dealing with a BS problem.

Now, what is that **positive** change?

=> if you draw a f(n) vs n graph and take slope at two points n1 & n2 where n1, n2 € [Domain of f(n)] then they must be of same type (either +ve or -ve) .

Let’s look at the following three graphs to understand it better. All three of them belong to same function** f(n) = n²** but with different domain (which is often called as search space in BS theory).

* Figure 1: n ≡ [1 , 10] *

* Figure 2 : n ≡ [-10 , -1]*

* Figure 3 : n ≡ [-10 , 10]*

considering n = 0 as a trivial case it’s clear from above that you can run a BS in first two cases but in the third case you can’t.

Feel free to discuss / correct anything.