A sequence (array) is really just a function which associates integers (indices) with the corresponding values. However, there is no reason to restrict our usage of binary search to tangible sequences. In fact, we can use the same algorithm described above on any monotonic function f. … The only difference is that we replace an array lookup with a function evaluation: we are now looking for some x such that f(x) is equal to the target value.

Source: TopCoder

Example

Problem: Given a perfect square S (such as 16129 = 127 * 127) between 1 and 10 ** 6, find its square root (assuming you don’t know how to calculate the square root).

Solution: Since the square is between 1 and 10 ** 6, we know that the square root must lie between 1 and 1000. We can keep halving this interval by taking the middle integer M in that range, and comparing M*M with S. For example, in the first step M = 500, and 500 * 500 > 16129, so the new range is 1 to 500. Note that we don’t need to compute the squares of all the numbers between 1 and 1000.

Check out the TopCoder tutorial if you want a lengthier more detailed explanation. The magic starts in section “Beyond arrays: the discrete binary search”.

To discuss this topic, check out the posts. And as always, feel free to ask questions!