题目的主要信息：

• 有一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，变成一个旋转数组
• 找到这个旋转数组的最小值
• 进阶要求：时间复杂度$O(lo{g}_{2}n)O(log\_2n)$，空间复杂度$O(1)O(1)$

方法一：遍历查找

具体做法：

直接遍历数组，每个数组元素与res比较，维护最小值即可。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int res = INT_MAX;
        for(int i = 0; i < rotateArray.size(); i++) //遍历数组
            res = min(res, rotateArray[i]); //每次维护最小值
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组大小，遍历一次数组
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外空间

方法二：二分法

具体做法：

因为旋转数组将原本有序的数组分成了两部分有序的数组，而无序的点就是最小的数字。

可以依旧利用二分的思想，分三种情况讨论：

• 情况一：若是区间中点值大于区间右界值，则最小的数字一定在中点右边；
• 情况二：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐渐缩减右界；
• 情况三：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。

通过调整区间最后即可锁定最小值所在。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(rotateArray[mid] > rotateArray[right]) //最小的数字在mid右边
                left = mid + 1;
            else if(rotateArray[mid] == rotateArray[right]) //无法判断，一个一个试
                right--;
            else //最小数字要么是mid要么在mid左边
                right = mid;
        }
        return rotateArray[left];
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，二分法最坏情况对$nn$取2的对数
• 空间复杂度：$O(1)O(1)$，无额外空间