Interview question - Search in sorted array X for index i such that X[i] = i

Question

I was asked the following question in my interview yesterday:

Consider a Java or C++ array say X which is sorted and no two elements in it are same. How best can you find an index say i such that element at that index is also i. That is X[i] = i.

As clarification she also gave me an example:

Array X : -3 -1 0 3 5 7 index   :  0  1 2 3 4 5  Answer is 3 as X[3] = 3. 

The best I could think was a linear search. After the interview I though a lot on this problem but could not find any better solution. My argument is: the element with the required property can be anywhere in the array. So it could also be at the very end of the array so we need to check every element.

I just wanted to confirm from the community here that I'm right. Please tell me I'm right :)

Answer 1

This can be done in O(logN) time and O(1) space by using a slightly modified binary search.

Consider a new array Y such that Y[i] = X[i] - i

Array X : -3 -1   0  3  5  7 index   :  0  1   2  3  4  5 Array Y : -3 -2  -2  0  1  2 

Since the elements in X are in increasing order, the elements in the new array Y will be in non-decreasing order. So a binary search for 0 in Y will give the answer.

But creating Y will take O(N) space and O(N) time. So instead of creating the new array you just modify the binary search such that a reference to Y[i] is replaced by X[i] - i.

Algorithm:

function (array X)         low  = 0        high = (num of elements in X) - 1         while(low <= high)                 mid = (low + high) / 2                 // change X[mid] to X[mid] - mid                if(X[mid] - mid == 0)                        return mid                 // change here too                else if(X[mid] - mid < 0)                        low = mid + 1;                 else                        high = mid - 1;        end while         return -1 // no such index exists...return an invalid index.  end function 

Java implementation

C++ implementation

Answer 2

There are some faster solutions, averaging O(log n) or in some cases O(log log n) instead of O(n). Have a google for "binary search" and "interpolation search", you're likely to find very good explanations.

If the array is unsorted, then yes, the element is anywhere and you can't get under O(n), but that's not the case with sorted arrays.

--

Some explanation on interpolation search as requested:

While the binary search only concerns with comparing two elements in terms of "greater / not greater", the interpolation search tries to also make use of numerical values. The point is: You have a sorted range of values from 0 to, say, 20000. You look for 300 - binary search would start at the half of range, at 10000. The interpolation search guesses that 300 would probably be somewhere closer to 0 than 20000, so it would check the element 6000 first instead of 10000. Then again - if it's too high, recurse into lower subrange, and it's too low - recurse into upper subrange.

For a big array with +- uniform distribution of values, interpolation search should behave much faster than binary search - code it and see for yourself. Also, works best if first you use one interpolation search step, then one binary search step, and so on.

Note that it's the thing a human does intuitively when looking up something in a dictionary.