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

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