题目内容：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 $1$。
数组可能包含重复项。

注意：

数组内所含元素非负，若数组大小为 $0$，请返回 $−1$。

数据范围

数组长度 $[0,90]$。

样例

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

这道题还是有三种思路，一种是暴力，一种是排序，一种是二分。

NO.1 暴力枚举

从前往后遍历一遍数组，找出数组中的最小值，返回。

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() == 0) return -1;
        int minn = 100;
        for (int i = 0; i < nums.size(); i ++)
            minn = min(minn, nums[i]);
        return minn;
    }
};

时间复杂度：$O(n)$

NO.2 排序

把数组从小到大排序，那第一个数就是我们的最小值。

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() == 0) return -1;
        sort(nums.begin(), nums.end());
        return nums[0];
    }
};

时间复杂度：$O(nlogn)$

NO.3 二分

我们可以把一个旋转数组分成两个单调递增的区间，像下图一样。

很显然答案是中间线右边的第一个数值，那么我们试想一下，如果能把右半部分的相同部分去掉，是不是就可以二分了呢？没错！左半边的数都$\geq num[0]$，右半边的数都$<num[0]$。
最优化的方案已经摆在眼前了，接下来就看如何实现了，具体细节见代码。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = nums.size() - 1;
        if (l < 0) 
            return -1;
        while (l > 0 && nums[l] == nums[0]) l --;//去掉右半部分相同的元素
        if (nums[l] >= nums[0])//如果nums[0]是最优解，就直接返回nums[0]
            return nums[0];
        int left = 0, right = l;//二分查找的第一个模板
        while (left < right)
        {
            int mid = left + right >> 1;
            if (nums[mid] < nums[0]) right = mid;//把区间分成[l, mid]与[mid + 1, r]
            else left = mid + 1;
        }
        return nums[right];
    }
};

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$