把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2}为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为 0，请返回 −1
样例
输入：nums = [2, 2, 2, 0, 1]
输出：0
分析：
- 理解二分法的本质：
寻找某种性质的分界点，只要可以找到某种性质，使得区间的前半部分满足，后半部分不满足，那么就可以用二分法把这个分界点找到。
对于本题：
发现除了最后水平的一段之外，其余部分满足二分性质：竖直线左边的数满足 nums[i]≥nums[0] 而竖直线右边的数不满足这个条件。
分界点就是整个数组的最小值。
所以我们先将最后水平的一段删除即可。
另外，要考虑到数组完全单调的特殊情况：
当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。
时间复杂度分析
二分的时间复杂度是 O(logn)，删除最后水平一段的时间复杂度最坏是 O(n)，所以总时间复杂度是 O(n)。
class Solution {
public:
//二分的时间复杂度是 O(logn)，
//删除最后水平一段的时间复杂度最坏是 O(n)，所以总时间复杂度是 O(n)。
int findMin(vector<int>& nums) {
// return nums.empty() ? -1 : *min_element(nums.begin(),nums.end());
int n = nums.size() - 1;
//若数组大小为 0，请返回 −1
if(n<0) return -1;
//把最后水平的一段重复元素去掉，便于后面的二分。
//把n=0的情况去掉（n=0时，数组长度为1，直接输出nums[0]即可）
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; //[l,mid] [mid+1,r]
if(nums[mid]<nums[0]) r=mid;
else l =mid+1;
}
return nums[l];
}
};
