【常见面试算法】旋转数组的最小值

问题

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例
输入：nums=[2,2,2,0,1]

输出：0

思路

参考 https://www.acwing.com/solution/acwing/content/727/

为了便于分析，我们先将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：

图中水平的实线段表示相同元素。

我们发现除了最后水平的一段（黑色水平那段）之外，其余部分满足二分性质：竖直虚线左边的数满足 nums[i]≥nums[0]nums[i]≥nums[0]；
而竖直虚线右边的数不满足这个条件。
分界点就是整个数组的最小值。

所以我们先将最后水平的一段删除即可。

另外，不要忘记处理数组完全单调的特殊情况：

当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。
时间复杂度分析
二分的时间复杂度是 O(logn)O(logn)，删除最后水平一段的时间复杂度最坏是 O(n)O(n)，所以总时间复杂度是 O(n)O(n)。

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length - 1;

        if(n < 0) return -1;

        //若数组尾巴存在水平，略过它们
        while (n > 0 && nums[n] == nums[0]) n--;

        //如果单调，则nums[0]即为最小值；若nums[n]==nums[0]，数组是水平的，也直接返回nums[0]。
        if(nums[n] >= nums[0]) return nums[0];
        //标准的二分查找
        int l = 0, r = n;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if(nums[mid] < nums[0]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}