Search algorithm and its complexity

Question

I was asked this question in an interview: Assume an infinite array of integers which is sorted. How would you search for an integer in this array? What would be time complexity? I guessed what the interviewer meant by infinite is that we dont know the value of 'n', where n is the index of the largest number in the array. I gave the following answer:

SEARCHINF(A,i,x){ // Assume we are searching for x
if (A(1) > x){
   return
}
if(A(i) == x){
   return i;
}
else{
    low = i;
    high = power(2,i);
    if (A(i)>x){
       BINARY-SEARCH(A,low,high);
    }
    else{
        SEARCHINF(A,high,x);
    }
}// end else
}// end SEARCHINF method

This will find the bound(low and high) in (log x + 1) time in the worst case, when the sorted numbers start from 1 and subsequent numbers are consequent. Then the binary search requires:

O( log {2^(ceil(log x)) - 2^(floor(log x))} )

Is this correct? If correct, can this be optimized?

Answer 1

Using the method of double your index until you pass it, then binary search the region you just jumped over (what it looks like your pseudocode is trying to do), the time spent should be O(log₂ n) where n is the index of the item you are searching for.

It will take you (log₂ n) tries to find the correct region, and then ((log₂ n) - 1) tries to find x within that region (since you already searched from 0..n/2, you only need to search n/2..n). Therefore, O(log₂ n + log₂ n - 1) = O(log₂ n).

However, if the "infinite array" does not contain x or any value greater than x, you will never know, because you will search forever.

Answer 2

The sorted array gives it away indeed: binary sort.

Worst case scenario: O(lg(n)). There's no faster, assured way of finding it.

Of course, you could just tell him that finding an element in an infinite array will take forever.