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

题目难度：简单
考察内容：暴力，二分
题目内容：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
问题分析
首先可以O(n)枚举求出最小值，时间复杂度O(n)，空间复杂度O(1)
代码如下

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int ans=1e9;
        //记录最小值
        for(int i=0;i<rotateArray.size();i++)
            ans=min(ans,rotateArray[i]);
        //更新最小值    
        if(rotateArray.size()==0)return 0;
        //特判数组为空，返回0
        return ans;
    }
};

明显不是最优解，没有用到单调性质
回到问题，将一个不降数组前几个数移到后面，这时候数组是两端不降数组，如图

当然，不一定是一直递增的，可能是平的，答在再第二段的最低点，如何确定第二段的最低点，下面进行分析

上面考虑了a[mid]和a[r]的关系，但是复杂度并不是严格O（logn）的可以同时考虑，a[mid]和a[l]吗？
无法同时进行，因为每次a[mid]只能和其中一个进行比较，所以和a[l]或者a[r]是一样的效果
代码如下

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int l=0,r=rotateArray.size()-1;
        //二分边界
        while(l<r)
        {
            int mid=l+r>>1;
            //中点
            if(rotateArray[mid]>rotateArray[r])
            {
                l=mid+1;
            //二分
            }
            else r--;
        }
        return rotateArray[l];
    }
};

时间复杂度O(log n)会退化为O（n）
空间复杂度O(1)