描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

思路1：遍历

直接遍历，找到比上一个元素小的元素，即最小值。时间复杂度O(n)

刷刷信心即可

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        for(int i = 1; i < array.length; i++) {
            if(array[i - 1] > array[i]) {
                return array[i];
            }
        }
        return array[0];
    }
}

思路2：二分查找

排序数组首先想到二分查找，时间复杂度O(logn)

需要注意的是中位数只能和右边比较，和左边比较存在问题，例如

• {1,2,3,4,5}：mid=3大于左边，最小值在左侧
• {3,4,5,1,2}：mid=5大于左边，最小值在右侧

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        //思路2：二分查找
        int l = 0;
        int r = array.length - 1;
        while(l < r) {
            //加法优先级比位运算高
            int mid = l + r >> 1;
            if(array[mid] > array[r]) {
                //中位数大于右边的数，则最小值在右半部分：[mid + 1, right]
                l = mid + 1;
            } else if(array[mid] < array[r]) {
                //中位数小于右边的数，则最小值在左半部分：[left, mid]
                //中位数有可能刚好是最小值，因此需要包含进来
                r = mid;
            } else {
                //如果相等则可能在左半部分，也可能在右半部分，此时缩小范围
                //例如1、2、3、3、3，或者3、3、3、1、3
                //只能缩小right的范围，因为right和mid相等，可以舍弃一个right。缩小left可能丢失数据
                r--;
            }
        }
        return array[l];
    }
}