What is this search algorithm called?

Question

I recently encountered an algorithm for searching for numbers in a sorted list and this is how it goes:

Given: An oracle that tells you if a given number greater than or less than the number being searched for.

Begin at first element in the list. Skip 1 element ahead and ask the oracle if you have gone ahead of the number being searched for.

If not, ask skip 2 elements and ask the oracle if you have gone too far.

If not skip 4 elements ahead, etc....

When you find the first skip that causes you to pass over the number being searched for, you can determine a subinterval that contains the number being searched for.

Finally, perform binary search on the subinterval.

I was wondering what this algorithm was called so that I might be able to do some more research on it.

Thanks

Answer 1

That's how you binary search an unbounded set.

For example, to solve an inequality f(n) < t over the positive integers, where f is an increasing function.

Concrete example:

Solve n**2 + 10*n < 100 over the positive integers.

Let f(n) = n**2 + 10*n for n > 0
f is increasing because it's the sum of increasing functions.

f(1) = 1 + 10 = 11
f(2) = 4 + 20 = 24
f(4) = 16 + 40 = 56
f(8) = 64 + 80 = 144 > 100

Now we binary search the interval [4,8]

f(6) = 36 + 60 = 96
f(7) = 49 + 70 = 119 > 100

Thus n < 7

Answer 2

This data structure is called Skip Lists

A skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n).

Answer 3

I would suggest few changes in the algorithm. There should be 2 iterators one following the other and when you realize that you have move to a list node which has greater number than the number being searched..we should restart the same steps with the previous iterator..this goes on till we find the number..because i dont understand how would to do a binary serch i.e in log(N) time with a list...