Search in infinite array using binary search

Question

Suppose, the array is infinite. So, the problem here is that we don’t know the size of the array. If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find the position of the key, what can I do.

Answer 1

It will no longer qualify as a pure binary search, but here's one approach.

For an array array and a search value s:

1. Decide on a block size n (e.g. n = 1000)
   Define an initial index i corresponding to the first element in the array (i = 1)
2. Compare the search value s to the value at array[n]
3. Then:
   1. If array[n] is greater than s:
      Continue with a regular binary search between array[i] and array[n]
   2. If array[n] is less than s:
      Move the index: i = i + n
      Double the block size: n = n * 2
      Start over at step 2.