Is there a name for this type of binary search?

Question

In writing some code today, I have happened upon a circumstance that has caused me to write a binary search of a kind I have never seen before. Does this binary search have a name, and is it really a "binary" search?

Motivation

First of all, in order to make the search easier to understand, I will explain the use case that spawned its creation.

Say you have a list of ordered numbers. You are asked to find the index of the number in the list that is closest to x.

int findIndexClosestTo(int x);

The calls to findIndexClosestTo() always follow this rule:

If the last result of findIndexClosestTo() was i, then indices closer to i have greater probability of being the result of the current call to findIndexClosestTo().

In other words, the index we need to find this time is more likely to be closer to the last one we found than further from it.

For an example, imagine a simulated boy that walks left and right on the screen. If we are often querying the index of the boy's location, it is likely he is somewhere near the last place we found him.

Algorithm

Given the case above, we know the last result of findIndexClosestTo() was i (if this is actually the first time the function has been called, i defaults to the middle index of the list, for simplicity, although a separate binary search to find the result of the first call would actually be faster), and the function has been called again. Given the new number x, we follow this algorithm to find its index:

1. interval = 1;
2. Is the number we're looking for, x, positioned at i? If so, return i;
3. If not, determine whether x is above or below i. (Remember, the list is sorted.)
4. Move interval indices in the direction of x.
5. If we have found x at our new location, return that location.
6. Double interval. (i.e. interval *= 2)
7. If we have passed x, go back interval indices, set interval = 1, go to 4.

Given the probability rule stated above (under the Motivation header), this appears to me to be the most efficient way to find the correct index. Do you know of a faster way?

Answer 1

In the worst case, your algorithm is O((log n)^2).

Suppose you start at 0 (with interval = 1), and the value you seek actually resides at location 2^n - 1.

First you will check 1, 2, 4, 8, ..., 2^(n-1), 2^n. Whoops, that overshoots, so go back to 2^(n-1).

Next you check 2^(n-1)+1, 2^(n-1)+2, ..., 2^(n-1)+2^(n-2), 2^(n-1)+2^(n-1). That last term is 2^n, so whoops, that overshot again. Go back to 2^(n-1) + 2^(n-2).

And so on, until you finally reach 2^(n-1) + 2^(n-2) + ... + 1 == 2^n - 1.

The first overshoot took log n steps. The next took (log n)-1 steps. The next took (log n) - 2 steps. And so on.

So, worst case, you took 1 + 2 + 3 + ... + log n == O((log n)^2) steps.

A better idea, I think, is to switch to traditional binary search once you overshoot the first time. That will preserve the O(log n) worst case performance of the algorithm, while tending to be a little faster when the target really is nearby.

I do not know a name for this algorithm, but I do like it. (By a bizarre coincidence, I could have used it yesterday. Really.)