题解 | #旋转数组的最小数字#

第三十六题 看到logn 就应该想到用二分法 找到变化的位置 也就是最小值

那么判断条件是什么？ 就看middle和最右边谁大 如果说middle比右边大，

1.假设数组是这样：456123  middle是6 right是3 那么显然 变化的值在右边middle和right中间

2.假设是412345 middle是2 right是5 说明右侧是正常的递增数列 所以变化的值必定在middle左边

3.假设是65412344 middle是4，right也是4，说明答案在middle和right中间，但因为中间不知道什么位置是旋转的地方，此时不能用二分法来找，只能让右边减一，再进入循环继续判断

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        // 二分法
        int left=0,right=rotateArray.size()-1;
        int middle=0;
        while(left<right){
            middle=(left+right)/2;
            
            // 如果中间的值比右边的大 则答案在右边
            if(rotateArray[middle] > rotateArray[right] )
                left=middle+1;
            
            // 如果中间的值比右边小 则答案在左边
            else if(rotateArray[middle] < rotateArray[right])
                right=middle;
            // 如果和最右边一样 答案在middle和right中间 继续只能缩小right--
            else
                right--;
        }
        return rotateArray[left];
    }
};