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