题目描述

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

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

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

数组可能包含重复项。

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

样例

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

输出：0

算法

(二分) $O(logn)$

先考虑一个最特殊的情况，如图所示

我们发现除了最后水平一段之外，满足前半段大于等于 nums[0]，后半段小于 nums[0]，根据这个性质就可以用二分二分出最小数

1. 特判 nums 为空
2. 先删除最后水平一段，如果删完之后数组单调就返回第一个数或者删完就剩一个数了就返回 nums[0]，否则就可以二分
3. 二分出小于 nums[0] 的最小的一个数即整个数组的最小值

时间复杂度

二分的时间复杂度是 $O(logn)$，删除最后水平一段的时间复杂度最坏是 $O(n)$，所以总的时间复杂度是 $O(n)$，但平均复杂度要小于 $O(n)$

C++ 代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;

        while (n > 0 && nums[0] == nums[n]) n -- ;
        if (!n || nums[n] > nums[0]) return nums[0];

        int l = 0, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};