What is the name for this search algorithm?

Question

A colleague came up with the following search algorithm:

• We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$]
• We are looking for the index of $i_k$ (for simplicity suppose that $i_k$ is in the array)
• We suppose that the elements are pretty uniformly distributed between $i_1$ and $i_n$

The algorithm:

1. let "position" be initially be 0
2. if $i_k$ == $i_{position}$, stop
3. otherwise:
   • calculate distance = $i_k$ - $i_{position}$
   • if we have just switched direction (eg. the previous distance was positive and this one is negative or vice-versa), make sure that abs(distance) < abs(previous distance) by adding/subtracting 1 from distance such that it gets closer to 0. Note: if distance is already is 1 or -1, it isn't adjusted.
   • let position be position + distance (see note below for possible optimization)
   • if position is positive, let position be min(position, n) (ie. don't overshoot the end)
   • if position is negative, let position be max(position, 0) (ie. don't undershoot the beginning)

I would be interested if somebody studied this algorithm and if so, what's its name? The best I could come up with is that it's a variant of "interpolation search", however I expect the above algorithm to be faster on x86 hardware because it only uses addition/subtraction which is faster than the division/multiplication used by "standard" interpolation search.

Note:

Instead of updating position by adding the distance (ie. position = position + distance) we can use the "average distance between consecutive elements" as a scaling factor: $$position \leftarrow position + distance / {i_n-i_0 \over n+1}$$

This should give a more precise estimate about the element position.

A disadvantage of the above is that it involves a division which is slow(er) on x86/x64 platforms. Perhaps we can get away with finding the closes power of two to the scaling factor (average distance between consecutive elements) and use shift to perform the division (ie. if $2^t$ is the power of two closes to the scaling factor we can do $position \leftarrow position + distance >> k$.

Update:

• as people have pointed out the initial element needs to be $i_0$
• added steps to avoid oscillating indefinitely between undershooting / overshooting the target
• discovered the "galloping search" from Timsort which seems related but not the same

Answer 1

You may be interested to a related algorithm, known as Interpolation Search, which achieves on average the complexity of $O(\log \log n)$ for searching $n$ keys. This is the usual search you do when you scan a phone book for example.

This paper discusses the algorithm, which was originally introduced earlier (1957) by Peterson.

Related data structures: dynamic interpolation search and interpolation search for non independent data.