Question : Given an infinite array of integers which is sorted. How would you search for an integer in this array? Here is the algo (in java):
public static int searchInf(int A\[\],int high,int x){
// Assume we are searching for x
if (A\[1\] > x){
return -1;
}
if(A\[high\] == x){
return high;
}
else{
int low = high;
int higher = (int) Math.pow(2,high);
if (A\[high\]>x){
binarySearch(A,low,higher);
}
else{
searchInf(A,higher,x);
}
}// end else
return -1;
}// end searchInf method
So if we find some element greater than element x, perform normal binary search, else call the search inf function.
Complexity
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(log2 n) where n is the index of the item you are searching for.
It will take you (log2 n) tries to find the correct region, and then ((log2 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(log2 n + log2 n - 1) = O(log2 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.