3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Doesn't this leave the minimum in an unusual place? $\endgroup$ – Bill Barth Jun 5 '15 at 13:55
  • $\begingroup$ 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. $\endgroup$ – hardmath Jun 7 '15 at 14:10
  • $\begingroup$ @Smallhacker I couldn't have put my question in different words. Almost as if you read my mind! $\endgroup$ – ManojRK Oct 11 '16 at 0:51
5
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Regarding name consensus: wikipedia gives en.wikipedia.org/wiki/Exponential_search, but I don't know how standard that name really is. It's not immediately recognizable to me. $\endgroup$ – Kirill Jun 5 '15 at 20:05
  • $\begingroup$ @Kirill, Good find! Editing to add. $\endgroup$ – Doug Lipinski Jun 5 '15 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.