CTCI 9.3

A magic index in an array A[1 ... n-1] is defined to be an index such that A[i] = 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.

CTCI 9.3-1.java

/*
-40, -20, -1, 1, 2, 3, 5, 7, 9, 12, 13
  0,   1,  2, 3, 4, 5, 6, 7, 8,  9, 10
*/
//distinct
public static int findMagicIndex(int[] array){
    if(array.length == 0) return -1;
    else return findMagicIndex(0, array.length - 1, array);
}

public static int findMagicIndex(int begin, int end, int[] array){
    if(begin < end) return -1;
    int mid = (begin + end) / 2;
    if(array[mid] == mid) return mid;
    else if(array[mid] < mid) return findMagicIndex(mid + 1, end, array);
    else if(array[mid] > mid) return findMagicIndex(begin, mid - 1, array);
}

CTCI 9.3-2.java

//not distinct
public static int findMagicIndex(int[] array){
    if(array.length == 0) return -1;
    else return findMagicIndex(0, array.length - 1, array);
}

public static int findMagicIndex(int begin, int end, int[] array){
    if(begin < end) return -1;
    
    int mid = (begin + end) / 2;
    if(array[mid] == mid) return mid;
    
    int leftIndex = Math.min(mid - 1, array[mid]);
    if(findLeft = findMagicIndex(begin, leftIndex, array) > -1) return findLeft;
    
    int rightIndex = Math.max(mid + 1, array[mid]);
    if(findRight = findMagicIndex(rightIndex, end, array) > -1) return fidRight;
    
    return -1;
}