# Does this "reverse binary search" have a name?

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).

• Doesn't this leave the minimum in an unusual place? Jun 5 '15 at 13:55
• Something of this kind is used in searching in one-dimension ("lines") for roots or optimums (minimums/maximums). The heuristic is to double the size of search "step" until a change in sign (of function or derivative, resp.) is detected. Look for "line searches" on the Internet for terminology used by various writers. Jun 7 '15 at 14:10
• @Smallhacker I couldn't have put my question in different words. Almost as if you read my mind! Oct 11 '16 at 0:51

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.