Binary search

Back to Algorithms

Let `n in NN`, and `f_n : NN --> {0, 1}` such that

Given `a in NN` such that `a <= n`, the problem is to find `n` using only evaluations of `f_n`.

This problem can be solved with the exponential binary search in `O(f log(n - a + 2))` time. If in addition `b in NN` is given such that `n < b`, then this simplified problem can be solved with the binary search algorithm in `O(f log((b - a) + 2))` time, where `O(f)` is the time taken by a single evaluation of `f_n`.

If the search interval is bounded (i.e. `b` is given), then the exponential binary search is not always faster than the binary search; at worst the exponential binary search uses twice as many comparisons as the binary search; see the notes for details.

References

An almost optimal algorithm for unbounded searching, Jon Louis Bentley, Andrew Chi-Chic Yao, Information Processing Letters, Volume 5, Issue 3, August 1976, pp. 82-87.

Learn more

Remark 1.7.5 - Page generated 16.06.2017 01:37.