剑指 Offer 11. 旋转数组的最小数字

题目链接

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

解1面向数据编程

测试数据比较弱直接排序就能过Orz

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

解2二分

正常大概是要二分的。。按照题意旋转后的数组大概是

 __/
/
       __/      
      /

这样的趋势。可以通过将中间的某个数与数组最后一位进行比较来舍弃一些区间。如果中间的数比最后一位大，说明最小值在这个数的右边，反正则在左边。需要注意的是有重复值的存在，如果一样大时无法确定，可以将最后一位左移一位。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low=0,high=numbers.size()-1;
        while(low<high)
        {
            int mid=low+(high-low)/2;
            if(numbers[mid]<numbers[high]) high =mid;
            else if(numbers[mid]>numbers[high]) low =mid+1;
            else high-=1;
        }
        return numbers[low];
    }
};