题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路一

最简单粗暴的方法，穷举出最小值，使得题意无意义，pass

public int minNumberInRotateArray(int[] array) {
    if (array == null || array.length == 0)
        return 0;
    else {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
}

解题思路二

对思路一进行优化，进行旋转后，数组最小值小于前一位

public int minNumberInRotateArray2(int[] array) {
    if (array == null || array.length == 0)
        return 0;
    else {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1])
                return array[i];
        }
        return array[0];  //数组值相同
    }
}

解题思路三

用类似二分查找的方法，不停收敛查找范围。

参考牛客解题https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba?answerType=1&f=discussion

807319133_1566217781994_E0D8DA4D79E73A35EB4365215E2F13BB.png

public int minNumberInRotateArray3(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    } else {
        int left = 0;  //范围的左边界
        int right = array.length - 1; //范围的右边界，由提意可得左部分>=右部分
        int middle;
        while (left < right) {
            if (array[left] < array[right])  //考虑到特殊情况10111
                return array[left];
            middle = (left + right) / 2;//取中间
            if (array[left] < array[middle]) {
                //证明[left...middle]区间仍在左部分，直接left右移到middle+1
                left = middle + 1;
            }else if(array[middle] < array[right]){
                //证明[middle.....right]区间在右部分，直接right左移到middle，而不是middle处，middle处可能是最小值
                right = middle;
            }else{
                //无法判断是在哪个部分，缩小区域
                left ++;
            }
        }
        return array[left];
    }
}