Finding A[i]=i in a sorted array with duplicates

Question

Given a sorted array of integers with possibly duplicates, how do you find an index i such that A[i]=i

This is a problem in one of the programming books I read (Cracking the code interview). The solution is outlined as follows:

 public static int magicFast(int[] array, int start, int end) {

    if (end < start || start < 0 || end >= array.length) {
     return -1;
     }

     int midlndex = (start + end) / 2;
     int midValue = array[midlndex];
     if (midValue == midlndex) {
       return midlndex;
     }

     /* Search left */
     int leftlndex = Math.min(midlndex - 1, midValue);
     int left = magicFast(array, start, leftlndex);
     if (left >= 0) {
     return left;
     }

     /* Search right */
     int rightlndex = Math.max(midlndex + i, midValue);
     int right = magicFast(array, rightlndex, end);
     return right;    
}

The author does not comment on the time complexity. However, this seems to be O(n) solution since we need to look at both sides of the 'mid' point unlike the problem where array elements are distinct. The recurrence relation being T(n) = 2T(n/2) + c (c - constant time to check if the middle element is the answer)

How is this better than a simple linear scan then? This seems overly complicated just to achieve linear time efficiency. Am I missing something here?

Answer 1

No, you're not missing anything. There's a short-circuit for the first branch, but the worst case is that both calls will be made, which results in a linear-time recurrence.

In fact, this problem has no sublinear-time algorithm by a simple cell probe lower bound. Consider the family of arrays a where

a(i) = i + 1 for i ≠ j
a(j) = j

for some j. These arrays are only distinguishable by examining the specific entry that is the fixed point, which implies a lower bound of n - 1 probes.

The original CTCI question I'm assuming did not allow duplicates -- then the modified array a(i) - i is nondecreasing, which allows binary search for the zero element.