CareerCup

the problem can be solved in two steps
1: find the range in which k exists.
2: find the index of k

traverse the array in power of 2
1:2^1<K<2^2 then the range is 2^1 and 2^2 apply binary search in this range
2:2^2<K<2^4 then the range is 2^2 and 2^4 apply binary search in this range
3:2^4<K<2^8 then the range is 2^4 and 2^8 apply binary search in this range
.
.
.
and so on.

Does n here refer to the interviewers IQ?

Is the question supposed to be in O(log(K)) time with an assumption that all integers in the array are unique?

Consider the case in which the whole array is composed of an infinite number of 1s, and k is 2. I think no algorithm will stop searching, as it cannot find 2 among all the numbers it has visited, while it cannot make sure 2 does not exist in the array and have to keep searching. In all, I think the numbers in the array should be distinctive

Since you know the maximum buffer size of your system.
take a file input having maximum size = Lmax.

now check value in which interval of value of K lies on.
like 0 to Lmaax,
Lmax+1 to 2*Lmax,
2*Lmax+1 to 3*Lmax
so on...............
for checking value ,we dont need to copy elements in the array...
we simply check value of (i-1)*Lmax and i*Lamx,if K lies between these range of value then we will copy all (i-1)*Lmax to i*Lamx within buffer;
now 'll perform Binary Search and will get the required solution.

if given numbers are in the file having total size T_size,
maximum buffer size = buf_size
then worst case = ((T_size/buf_size) -1) + log(buf_size)

// arr is the name of infinite array
int i = 1<<0x1;
while (arr[i]<k)
{
i = i << 1;
}

// jump out the while loop means that the 'k' locates between arr[i/2] and arr[i]
// then binary search k between arr[i/2] and arr[i]

oh, seems the same as 'kamal' said.
but the time complexity of this method seems not log(k).
em, thinking...

I am thinking like we have to do binary search by dividing the the number of elements. i.e. take a set of k elements try to do binary search this takes logk for k elements.. In that way it goes like this logk + log k + logk + ....... = constant* logk
which inturn would become logk.. what is your opinion on this ?

Let me clarify here about infinite array.
We are not going to run our program on hypothetical machine where there is infinite space.

So infinite here means that we don't know the size of the array.

Now you have got two ways either find out the size of array which I guess according to interviewer is not allowed.
I was asked the similar question and after asking he said that if we are trying to access an element that is not in array bound it will return an error code.

So , the solution will come up as exponential jump.

//arr is the infinite array
int a=0; n=arr.lenght(); // start and end of the array

while(arr[mid]==k)
{

mid =(n+a)/2; //lower bound
if ( arr[mod] < k)
a=mid + 1;
else
n=mid-1;

}
print 'mid';