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

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 o开发者_运维知识库f 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 :)

---

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

---

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.

---

Its not require to think in terms of any array Y as suggested in answer by @codaddict.

Use binary search and check the middle element of given array, if it is lower than its index, than we do not need to check for any lower index because the array is sorted and so if we move to the left, subtracting m indexes and (at least) m value, all subsequent elements will also be too small. E.g. if arr[5] = 4 then arr[4] <= (4 - 1) and arr[3] <= (4 - 2) and so on. Similar logic can be apply if middle element is greater than its index.

Here is simple Java implementation:

int function(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        while(low <= high) {
            int mid = high - (high - low) / 2;

            if(arr[mid] == mid) {
                 return mid;
            } else if(arr[mid] < mid) {
                 low = mid + 1;
            } else {
                 high = mid - 1;
            }
        }

        return -1; // There is no such index
}

Note that the above solution would work only if all elements are distinct.

---

I think this would be faster.

Start in the middle of the list

If X[i] > i then go to the middle of the remaining left side

if X[i] < i then go the middle of the remaining right

Keep doing that and it will reduce the number of possible elements by half for each loop

---

You can perform a binary search: search the middle, if the value is lower than the index, than no lower index will contain the same value.

Then you search the higher half, and continue till you find the element, or reach one element span.

---

This is a solution I came up with, and it works if there are duplicates (I mistakenly overlooked that caveat of there being no duplicates).

//invariant: startIndex <= i <= endIndex

int modifiedBsearch(int startIndex, int endIndex)
{
   int sameValueIndex = -1;
   int middleIndex = (startIndex + endIndex) /2;
   int middleValue = array[middleIndex];
   int endValue = array[endIndex];
   int startValue = array[startIndex];

   if(middleIndex == middleValue)
      return middleValue;
   else {
      if(middleValue <= endIndex)
         sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex)

      if(sameValueIndex == -1 && startValue <= middleIndex)
         sameValueIndex = modifiedBsearch(startIndex, middleIndex -1);
   }

   return sameValueIndex;

}

I would guess this takes O(log n) time, but this isn't clear in first glance???

If you're unlucky, it'll take O(n log n) time (the height of the stack tree will be log n, and it will be a full tree, with n nodes in the last level, n/2 in next to last, etc.).

So, on average it will be between O(log n) and O(n log n).

---

of the top of my head, doing binary splitting might be faster.

look at the middle value, if it is high then what you need, re-search in the lower half.

After one comparison, you have already spilt your data set in half

---

After reading the question it seems like there is one scenario that can be used to speed up the lookup. When comparing the position to the value, if the value is greater then the position then the value can be used as the next position to evaluate. This will help jump through the array faster. This can be done because the array is sorted. The values that we are skipping are conceptually shifted to the left in the array and are in the wrong location.

Example:

int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };

If my current position is 2 and it has a value of 4 they are not equal and conceptually the value 4 is shifted to the left. I can use the value of 4 as my next position because if the value 4 is out of position then everything less then 4 is out of position as well.

Some example code just for the sake of discussion:

void main()
{
    int X[] = { -3, -1, 0, 3, 5, 7};
    int length = sizeof(X)/sizeof(X[0]);

    for (int i = 0; i < length;) {
        if (X[i] > i && X[i] < length)
            i = X[i];                 // Jump forward!
        else if (X[i] == i) {
            printf("found it %i", i);
            break;
        } else
            ++i;
    }
}

---

Modified version of Binary Search would suffice I guess

Suppose the sequence is

Array : -1 1 4 5 6
Index :  0 1 2 3 4

Result : 1

or

Array : -2 0 1 2 4 6 10
Index :  0 1 2 3 4 5 6 

Result: 4

From both the examples we see that the required result will never lie on the right side if mid < a[mid]... pseudocode would look something like this

mid <- (first + last )/2

if a[mid] == mid then
       return mid

else if a[mid] < mid then
        recursive call (a,mid+1,last)

else 
         recursive call (a,first,mid-1)

---

Java:

public static boolean check (int [] array, int i)
{
    if (i < 0 || i >= array.length)
        return false;

    return (array[i] == i);
}

C++:

bool check (int array[], int array_size, int i)
{
    if (i < 0 || i >= array_size)
        return false;

    return (array[i] == i);
}