Searching the element in sorted infinite array of integers
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.
[Read More]