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

1. 这就是简单的二分法的变体。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(!rotateArray.size()) return 0;

        int begin = 0, end = rotateArray.size()-1;
        while(begin < end){
            if(rotateArray[begin]<rotateArray[end]){//必然第一个是最小的，因为旋转数组具有首元素大于末尾元素的性质。
                return rotateArray[begin];
            }

            int  mid = (begin+end)/2;
            if(rotateArray[mid] > rotateArray[end] ){
                begin = mid+1;//答案必然在mid后面。不可能是mid本身
            }else if(rotateArray[mid] < rotateArray[end]){
                end = mid;//因为有可能中点就是答案。
            }else{
                end--; //因为是一个非递减序列
            }


        }

        return rotateArray[begin];
    }
};