二分法

• 利用单调性，来判断最小值所在的区间。
• 当nums[mid]==nums[right]是无法判断的，[0,1,1,1,1]在左边，[2,3,4,1,1,1,1]自己本身，[2,2,2,1,2]在右边。
• 通过right-1来缩写范围，原理，每次都不会排除最小值。旋转个数为0时，此时时间复杂度是O(n)。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int min_val=0;
    void find_min(vector<int>& nums,int left,int right)
    {

        if(right<left)
        {
            return;
        }
        if(right==left)
        {
            min_val=nums[right];
            return;
        }
        int mid=(left+right)/2;
        int min_val=nums[right];
        if (nums[mid]<min_val)
        {
            //最小值在mid的左边/mid
            find_min(nums,left,mid);

        }
        else if(nums[mid]>min_val)
        {
            //最大值在mid的右边
            find_min(nums,mid+1,right);

        }
        else{
            //无法判断
            find_min(nums,left,right-1);

        }
    }
    int minNumberInRotateArray(vector<int>& nums) {
        // write code here
        min_val=nums[nums.size()-1];
        find_min(nums,0,nums.size()-1);
        return min_val;

    }
};