题目描述

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

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

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

数组可能包含重复项。

样例

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

输出：0

算法

(二分)

1. 对于二分，我一直推荐的是，自己先在纸上画出2个区间，然后看看mid会出现在哪个区间，一般是左右2个区间，答案到底的左边区间的 右上角端点，还是右边区间的 左上角端点。然后通过mid位置的不同来判断l和r的更新情况。
2. 这道题左边区间是>= nums[0]，右边区间是< nums[0]的，两个区间都是升序的，答案是< nums[0]的最小值，那么就是右边区间的左上角端点，所以如果mid处于< nums[0]这个区域，因为ans在区域的最左边，所以让r = mid，从而让整体的区间向左滑，不断二分出ans。
3. 在进行二分前，有2个需要注意的，第一个，去掉尾部的重复元素，也就是< nums[0]区间的尾部如果跟nums[0]相同，则去掉，因为不去掉就不能二分了。
4. 如果右边区间在去重完后右边区间没有了，或者本身输入的就是个完全单调的区间，那么就不需要二分了，如果接着二分，就会出现输出nums[n - 1]的情况，也就是数组的 最大值。既然不需要二分，就提前判断if(nums[idx] >= nums[0])(上面2种情况自己模拟下)，然后return nums[0]。
5. 其实二分的本质是，找到一个边界点，这个边界点可以划分区间为2个性质完全相反的子区间，重点是这个边界点需要是ans，而不是其他的。比如这道题边界点是 最小值min，但我一开始找成了nums[0]。这道题二分的性质不是 min的右边的元素都大于等于min，但是都小于A[0]， 左边的元素也许都比min大，但是均大于等于A[0]。而不是简单地拿A[0]作为划分的边界。

时间复杂度

$O(n)$
二分的时间复杂度是$O(logn)$，删除 最后一段水平重复元素的时间复杂度最坏是$O(n)$，所以最终答案是$O(n)$

C++ 代码

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

        int idx = n - 1;
        while(idx >= 0 && nums[idx] == nums[0]) idx --;    // **2

        if(nums[idx] >= nums[0]) return nums[0];         // **1

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