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

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

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

数组可能包含重复项。

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

样例

1
2
3

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

输出：0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(0 == nums.size()) return -1;
        int l = 0 ,r = nums.size() - 1;
        while(r > 0 && nums[r] == nums[0]) --r;
        if(nums[r] >= nums[0]) return nums[0];//一定是升序
        //只有下面这种情况的可能
        
        /*
                9   9            
              8  
            7           
                            2
                        1
            [1,2,7,8,9,9]
        */
        while (l<r) {
            int mid = l+r >>1;
            if(nums[mid] < nums[0]) r = mid;//[l..mid] 有最小值
            else if(nums[mid]>= nums[0]) {
                //在 [mid + 1,r]中
                //比如 nums[mid ] = 8,nums[0] = 7, 最小值是后面的 1
                l = mid + 1;
            }
        }
        return nums[r];
    }
};