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