二分-局部最小

寻找数组局部最小值

解答思路：

只要有最小值，那我就可以找到。

a[0] <= a[1], 则a0就是极小值；
a[n - 2] >= a[n - 1], 则a[n-1]就是极小值

否则，就如图(一定有最小值）：

public static int localMinimum(int[] x) {
    if (x == null || x.length == 0) {
        return -1;
    }
    if (x.length == 1 || x[0] < x[1]) {
        return 0;
    }
    if (x[x.length - 1] < x[x.length - 2]) {
        return x.length - 1;
    }

    int mid = 0;
    int left = 1;
    int right = x.length - 2;
    while (left < right) {
        mid = (left + right) / 2;
        if (x[mid - 1] < x[mid]) {
            right = mid - 1;
        } else if (x[mid + 1] < x[mid]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
}