A magic index in an array A[0...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?

public int getMagicIndex(int[] inputs) {        return helper(0, inputs.length - 1, inputs);    }    private int helper(int start, int end, int[] inputs) {        if(end < start)             return -1;        int mid = (end - start) / 2 + start;        if(mid == inputs[mid]) {            return mid;        } else if (mid > inputs[mid]) {            return helper(mid + 1, end, inputs);        } else {            return helper(start, mid - 1, inputs);        }    }

Follow Up: 看答案的

/**     *      * A magic index in an array A[0...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?     *      */    public static void main(String[] args) {        // TODO Auto-generated method stub        int[] inputs = {-11, -9, -3, -3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 16};        System.out.println(getMagicIndex(inputs));    }    public static int getMagicIndex(int[] inputs) {        return helper(0, inputs.length - 1, inputs);    }    private static int helper(int start, int end, int[] inputs) {        if(end < start)             return -1;        int midIndex = (end - start) / 2 + start;        int midValue = inputs[midIndex];                if(midIndex == midValue) {            return midIndex;        } else {            // Search left            int leftIndex = Math.min(midIndex - 1, midValue);            int left = helper(start, leftIndex, inputs);            if(left > 0) {                return left;            }            // Search right            int rightIndex = Math.max(midIndex + 1, midValue);            return helper(rightIndex, end, inputs);        }    }