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));    }}