9.3 寻找magic index

在A[0..n-1]中，满足条件 A[i]==i的索引。

给定一个有序数组，设法找到其中的magic index。

扩展：考虑有重复元素的情况如何处理。

public class Solution {

    public static int magicIndex(int[] array) {
        return magicDup(array, 0, array.length - 1);
    }

    /**
     * 非递归，有重复情况可能有问题
     */
    private static int magic(int[] a, int left, int right) {

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] < mid) {
                left = mid + 1;
            } else if (a[mid] > mid) {
                right = mid - 1;
            } else
                return mid;

        }
        return -1;
    }

    /**
     * 递归写法，能够处理有重复的情况
     */
    private static int magicDup(int[] a, int left, int right) {
        if (left > right)
            return -1;

        int mid = left + (right - left) / 2;
        if (a[mid] == mid)
            return mid;
        int leftIdx = Math.min(mid - 1, a[mid]);
        int leftEnd = magicDup(a, left, leftIdx);
        if (leftEnd >= 0)
            return leftEnd;

        int rightIdx = Math.max(mid + 1, a[mid]);
        int rightEnd = magicDup(a, rightIdx, right);
        return rightEnd;

    }

    public static void main(String[] args) {
        int[] a = { 0, 2, 4, 5 };
        System.out.println(magicIndex(a));
    }
}