Does this "reverse binary search" have a name?

Question

Normally when searching in sorted sets, binary searches are a fast, nice and easy way to locate data. It does however break down in the hypothetical scenario of having a set of arbitrarily large but unknown size as it cannot have its upper limit set to infinity.

In order to solve this, one could imagine doing a, for lack of a better term, "reverse binary search" to find rough lower/upper limits, then perform a regular binary search:

min = 0
max = 1
while( set[max] exists && set[max] < target ) {
    min = max + 1
    max *= 2
}
binarySearch(min, max)

Since this seems to be a somewhat trivial algorithm, I cannot possibly be the first one to think of it, so my question is simply whether this algorithm has a name (and if so, what it is).

Answer 1

This seems to be called an exponential search, doubling search, or galloping search. I've also heard it called a geometric expansion search or something similar. In principal, it is similar to the geometric expansion strategy that is often used for resizing dynamic arrays in computer programming. Resizing dynamic arrays in this way ensures that adding $n$ elements takes $\mathcal{O}(n)$ time. This does not necessarily rely on doubling the storage each time, you could use a factor of 3 or 3/2 or any other number greater than 1.

If you use this method to find an upper bound for an interval and then use a binary search to find the exact element you would need $\mathcal{O}(\log_2(N))$ for each part of the algorithm where N is the index of the entry that is eventually found. Averaged over many searches, I think this would be an optimal search strategy if the probability that you will need to find entry $N$ is proportional to $1/N$. In other words, this would be a good strategy to use if you expect to preferentially choose points that are near the beginning of your array.

In a continuous setting this would be useful if you were trying to find where a function reaches a certain value and all you know is that the function grows approximately exponentially. You could use the binary expansion search to find a range that encompasses the value you want and then use a binary search to narrow down on the precise value. Of course there are faster search methods in this case (taking better advantage of your knowledge of the function or using higher order search methods), especially for well-behaved functions, but this would allow you reasonable efficiency with a very simple method.