题解 | #旋转数组的最小数字#

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        return getMin(array, 0, array.length - 1);
    }

    public int getMin(int[] array, int start, int end) {
        if (start == end) {
            return array[start];
        }
        int midIndex = (start + end) / 2;
        int mid = array[midIndex];
        int left = array[start];
        int right = array[end];

        if (mid > left &&
                mid < right) { //大于左边值，小于右边值，则说明是是升序，左边值则是最小值
            return left;
        } else if (mid >
                   right) { // 如果mid大于右边的值，则说明在mid和右边之间
            return getMin(array, Math.min(midIndex + 1, end), end);
        } else if (mid >
                   left) { // 如果mid 小于左边的值，则说明左边和mid之间
            return getMin(array, start, Math.max(midIndex - 1, start));
        } else {
            int leftMin = getMin(array, start, Math.max(midIndex , start)); // 这里没有减1，是因为这里如果减1可能会导致少一个值，midIndex可能就是最小的值会丢掉
            int rightMin = getMin(array, Math.min(midIndex + 1, end), end);
            return Math.min(leftMin, rightMin);
        }

    }




}