News‎ > ‎

Exponential binary search

posted Apr 19, 2011, 2:00 PM by Håkan Jonsson
The way to search an unbounded sorted array I showed today is called exponential binary search. It is attributed to Jon Bentley (in fact, the very same man behind the plane sweep technique over line segments we learned about in Chapter 2) and Andrew Yao (a very prominent computer scientist with deep knowledge and insights about complexity theory and who, according to rumor, is one of those that might solve the famous N=NP?- problem) who first wrote a report that was later published.

The idea is to look at indices that we double again and again until we reach an index such that the number stored in the array at that index is larger than the one we are looking for. We can then do a "regular" binary search in the array and between the last and second last index. Total time O(log n) time if the number we are looking for lies at an index less than 2n.

My example included a memory of finite, but unknown, length. In the search we here got an error message (or an interrupt, or a signal) as soon as we use a too large index. But the idea is the same - first exponential binary search to find something too large, then a regular binary search to find the true end of the memory.