剑指offer11 旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

示例 1：

输入：[3,4,5,1,2] 输出：1

示例 2：

输入：[2,2,2,0,1] 输出：0

思路

一开始我就想到了一种方法，因为这是一个旋转的有序数组，所以最小值一定是小于它前面的那个数的，所以我们只需要找到第一个不服从升序的数，找不到就返回数组第一个数。

class Solution {
public :
int minArray(vector<int>& numbers) {
        for (int i = 0; i < numbers.size() - 1; i++) {
            if (numbers[i] > numbers[i + 1]) return numbers[i + 1];
        }
        return numbers[0];//顺序排就返回第一个
    }
};

当然你可以懒一点，排个序然后直接返回第一个数（你可以借机会自己写一写快排，归并）

class Solution {
public:
    int minArray(vector<int>& numbers) {
        sort(numbers.begin(),numbers.end());
        return numbers[0];
    }
};

但其实，面对有序或者半有序的数列，应该想到二分查找。 旋转数组的最后一个元素有一个性质，最小值左边的数必定大于它，最小值右边的数必定小于它，我们可以以此进行二分

• 当numbers[r] > numbers[mid]时，最小值必定是在中点的左边或就是中点，所以可以丢弃中点右边的范围
• 当numbers[r] < numbers[mid]时，最小值必定是在中点的右边，所以可以丢弃中点右左的范围
• 当numbers[r] == numbers[mid]时，不能确定最小值的具体范围，就缩小边界，再进行二分

class Solution {
public:
    int minArray(vector<int>& numbers) {
        //二分
        int l = 0, r = numbers.size() - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            //序列最后一个数，最小值左边的数必定大于它，最小值右边的数必定小于它
            if(numbers[r] > numbers[mid]) r = mid;//
            else if(numbers[r] == numbers[mid]) r--;//
            else l = mid + 1;//
        }
        return numbers[l];
    }
};