把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。

輸入一個(gè)升序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。

例如數(shù)組 {3,4,5,1,2}為 {1,2,3,4,5} 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為 1

數(shù)組可能包含重復(fù)項(xiàng)。

注意：數(shù)組內(nèi)所含元素非負(fù)，若數(shù)組大小為 0，請(qǐng)返回 ?1

樣例

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

輸出：0

分析：

• 理解二分法的本質(zhì)：
  尋找某種性質(zhì)的分界點(diǎn)，只要可以找到某種性質(zhì)，使得區(qū)間的前半部分滿足，后半部分不滿足，那么就可以用二分法把這個(gè)分界點(diǎn)找到。

對(duì)于本題：

發(fā)現(xiàn)除了最后水平的一段之外，其余部分滿足二分性質(zhì)：豎直線左邊的數(shù)滿足 nums[i]≥nums[0] 而豎直線右邊的數(shù)不滿足這個(gè)條件。
分界點(diǎn)就是整個(gè)數(shù)組的最小值。
所以我們先將最后水平的一段刪除即可。

另外，要考慮到數(shù)組完全單調(diào)的特殊情況：
當(dāng)我們刪除最后水平的一段之后，如果剩下的最后一個(gè)數(shù)大于等于第一個(gè)數(shù)，則說明數(shù)組完全單調(diào)。

時(shí)間復(fù)雜度分析
二分的時(shí)間復(fù)雜度是 O(logn)，刪除最后水平一段的時(shí)間復(fù)雜度最壞是 O(n)，所以總時(shí)間復(fù)雜度是 O(n)。

class Solution {
public:
    //二分的時(shí)間復(fù)雜度是 O(logn)，
    //刪除最后水平一段的時(shí)間復(fù)雜度最壞是 O(n)，所以總時(shí)間復(fù)雜度是 O(n)。
    int findMin(vector<int>& nums) {
        // return nums.empty() ? -1 : *min_element(nums.begin(),nums.end());
        int n = nums.size() - 1;
        //若數(shù)組大小為 0，請(qǐng)返回 ?1
        if(n<0) return -1;
        //把最后水平的一段重復(fù)元素去掉，便于后面的二分。
        //把n=0的情況去掉（n=0時(shí)，數(shù)組長(zhǎng)度為1，直接輸出nums[0]即可）
        while (n>0 && nums[n] == nums[0]) n--;
        //去掉最后水平的一段后，如最后一個(gè)數(shù)大于等于第一個(gè)數(shù)，則數(shù)組完全單調(diào)。
        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];
    }
};