题目描述

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

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

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

数组可能包含重复项。

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

样例

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

输出：0

算法1

(二分法) $O(n)$

int l = 0, r = n - 1;
while( l < r){
    if(check()) r = mid ;
    else l = mid + 1;
}
return l;

时间复杂度

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

参考文献

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

C++ 代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        //前后两端可能的数可能相同
        int n = nums.size() -1 ;

        if(nums.empty()) return -1;

        while(n > 0 && nums[n] == nums[0]) n --;    
        //最后一个数大于等于第一个数，说明第一个数就是最小的
        if(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[r];       
    }
};