Question9_3.java

/**
 * A magic index in an array A[1.. .n-1] is defined to be an index such that A = i.
 * Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.
 * 
 * FOLLOW UP
 * What if the values are not distinct?
 */

public class Question9_3 {
    /*
     * Time  Complexity: O(logn)
     * Space Complexity: O(1)
     */
    public int magicIndex(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = array.length - 1;
        
        while (left <= right) {
            int middle = (right - left) / 2 + left;
            if (array[middle] > middle) {
                right = middle - 1;
            } else if (array[middle] < middle) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        
        return -1;
    }
    
    
    /*
     * Time  Complexity: O(n)
     * Space Complexity: O(1)
     */
    public int magicIndexNotDistinct(int[] array, int left, int right) {
        if (array == null || array.length == 0 || left > right) {
            return -1;
        }
        
        int middle = (right - left) / 2 + left;
        if (middle == array[middle]) {
            return middle;
        }
        
        int leftResult = magicIndexNotDistinct(array, left, Math.min(array[middle], middle - 1));
        if (leftResult >= 0) {
            return leftResult;
        }
        
        int rightResult = magicIndexNotDistinct(array, Math.max(array[middle], middle + 1), right);
        if (rightResult >= 0) {
            return rightResult;
        }
        
        return -1;
    }
    
    
    public static void main(String[] args) {
        Question9_3 question9_3 = new Question9_3();
        int[] array = new int[] {0, 2, 3, 4, 5, 6};
        System.out.println(question9_3.magicIndex(array));
        
        array = new int[] {0, 0, 0, 2, 3, 3, 5, 6};
        System.out.println(question9_3.magicIndexNotDistinct(array, 0, array.length - 1));
    }
}