which associates integers (indices) with the corresponding values. However, there is no reason to restrict our usage of binary search toA sequence (array) is really just a functionsequences. In fact, we can use the same algorithm described above ontangible... 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.any monotonic function f.

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!