题目描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。
请问，给定这样一个旋转数组，求数组中的最小值。

题解1：使用库函数sort或者小根堆

代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
//         题解1：直接排序处理
        sort(rotateArray.begin(),rotateArray.end());
        return rotateArray[0];
        
        //题解2：小根堆
        priority_queue<int,vector<int>,greater<int>> q;
        for(int i =0;i<rotateArray.size();i++){
            q.push(rotateArray[i]);
        }
        return q.top();
        }
    }
};

题解2：二分法

算法思路：

1. 由于数组是递增的，所有可以* 把target 看作是右端点*
2. 然后进行二分查找最小值
3. 分析得到不能* 把target 看作是左端点

代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size()-1;
        int mid = 0;
        while(left <= right){
            mid = (left+right)/2;
            if(rotateArray[mid] <= rotateArray[right])
                right = mid;//中间小于右边，小值要么是中间值要么是中间值的左边
            else if(rotateArray[mid] > rotateArray[right])
                left = mid +1;//中值大于右边，小值肯定在中值得右边
            else //if(rotateArray[mid] = rotateArray[right])
                right--;//中值等于右值，不能判断小值的位置，但小值肯定不在right处
        }
        return rotateArray[left];
        }
    }
};