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?

Vaughan

@HenkHolterman: If left < 0, then the algorithms goes on to searching right. So, worst case, it searches both sides of the array unlike a typical binary search which assures only looking at one half of the array, right? – Vaughan

Yes, it's a little more involved than with a regular binary search. I read that part wrong. – Prophecy

Unless your focus is solely worst case behavior, then this is still better than a simple linear scan because it can often perform sublinearly. – Pesthole

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.

Opalopalesce

Yes, the original version of the problem has only distinct elements – Vaughan