Problem Identification: Binary Search

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.

Read more…(193 words)

About the author:

Rafat Islam

Loading…

Join the discussion. Add a reply…

Post

About the author

Rafat Islam

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.