Find an element in an infinite length sorted array

Question

Given an infinite length sorted array having both positive and negative integers. Find an element in it.

EDIT
All the elements in the array are unique and the array in infinite in right direction.

There are two approaches:

Approach 1:

Set the index at position 100, if the element to be found is less, binary search in the previous 100 items, else set the next index at position 200. In this way, keep on increasing the index by 100 until the item is greater.

Approach 2:

Set the index in power of 2. First set the index at position 2, then 4, then 8, then 16 and so on. Again do the binary search from position 2^K to 2^(K + 1) where item is in between.

Which of the two approaches will be better both in best case and worst case?

Answer 1

The first approach will be linear in the index of the element (O(k) where k is the index of the element). Actually, you are going to need k/100 iterations to find the element which is greater than the searched element, which is O(k).

The second approach will be logarithmic in the same index. O(logk). (where k is the index of the element). In here, you are going to need log(k) iterations until you find the higher element. Then binary search between 2^(i-1), 2^i (where i is the iteration number), will be logarithmic as well, totaling in O(logk)

Thus, the second is more efficient.

Answer 2

You can apply binary search more or less directly with a small modification. This will roughly correspond to your Approach 2.

Basically, pick some number B and set A to 0, then check if the element you're looking for is between A and B. If it is, perform the usual kind of binary search in these boundaries, otherwise set B=A and A=2*A and repeat. This will take O(log(M)), where M is the position of the element you're looking for in the array.