package Twitter;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Bella
 * @version 1.0
 * @Date 11/7/17 6:10 PM
 */
public class MagicIndex {
    public static void main(String[] args) {
        int[] array = {-1, 2, 2, 2, 3 ,4 ,7, 8};

        List<Integer> result = new ArrayList<Integer>();

        int start = 0;
        int end = array.length - 1;

        System.out.println(helper(array, start, end));
    }

    static int helper(int[] array, int low, int high) {
        if (low > high || low < 0 || high >= array.length) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (array[mid] == mid) {
            return mid;
        }
        int left = Math.min(mid - 1, array[mid]);
        int leftRes = helper(array, low, left);
        if (leftRes != -1) {
            return leftRes;
        }
        int right = Math.max(mid + 1, array[mid]);
        return helper(array, right, high);
    }

}