Search Algorithm and Its Complexity

Question

I was asked this question in an interview: suppose an infinite array of integers is sorted. How would you look for an integer in this array? What will be the time complexity? I guessed that the interviewer meant infinite, so that we do not 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 

In the worst case, the associated (low and high) value (log x + 1) will be found when the sorted numbers start at 1 and subsequent numbers. Then for binary search you need:

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

It is right? If this is correct, can this be optimized?

Answer 1

Using the double index method until you skip it, then do a binary search in the region in which you just jumped (what it looks like, how it tries to execute pseudocode), the elapsed time should be O (log ₂ n), where n is the index the item you are looking for.

You will need (log ₂ n) trying to find the correct region, and then ((log ₂ n) - 1) trying to find x in this region (since you already searched with 0..n / 2, you only need to search for 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

A sorted array really highlights this: binary sorting.

Worst case scenario: O (lg (n)). There is no faster or surer way to find it.

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