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

一.题目描述
JZ6 旋转数组的最小数字
原题链接:https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目大意:把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
二.算法1(投机取巧的方法)
本质是找出最小的数字,所以我们可以利用最小数字这个特点直接找出最小的数字

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0){
            return -1;
        }
        int mx=rotateArray[0],u=0;//因为所以数字都是大于0的,所以刚开始最大值为0
        for(int i=1;i<rotateArray.size();i++){
            if(rotateArray[i]<rotateArray[i-1]){
                u=i;
                break;
            }
        }
        return rotateArray[u];
    }
};

复杂度:o(n)
优缺点:可以快速过题目,但是不能真正得到锻炼,作者建议大家看看图一个乐
三.算法二(二分)
为了便于分析，我们先将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：

图中水平的实线段表示相同元素。
我们发现除了最后水平的一段（黄色水平那段）之外，其余部分满足二分性质：
竖直虚线左边的数满足rotateArray[i]≥rotateArray[0]nums[i]≥nums[0]；
而竖直虚线右边的数不满足这个条件。分界点就是整个数组的最小值。所以我们先将最后水平的一段删除即可。
另外，不要忘记处理数组完全单调的特殊情况：删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int n = rotateArray.size()-1;
        if (n<0) return -1;
        while (n>0&&rotateArray[n] == rotateArray[0]) n--;
        if (rotateArray[n] >= rotateArray[0]) return rotateArray[0];
        int l = 0, r = n;
        //二分查找
        while (l<r) {
            int mid=l+r>>1;//加法的优先级高于位运算 所以不需要加括号
            if (rotateArray[mid]<rotateArray[0]) r=mid;
            else l=mid+1;
        }
        return rotateArray[r];

    }
};

复杂度:o(n)
优缺点:时间效率很高,但是实现比较复杂