【剑指 offer】旋转数组的最小数字

1、题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

• 注意：数组内所含元素非负，若数组大小为0，请返回-1。

• 样例

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

2、问题描述：

• 排好序的数组，将数组的前面某一部分移动到后面。
• 求数组的最小的元素。

3、问题关键：

• 前一半是递增的，后一半递增的。

• 注意最后面的元素可能等于最开始的元素，要去掉。

• 二分法可以做，如果mid < r， 说明递增，那么区间在前一半。r = mid。
  

4、C++代码：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return -1;
        while(n > 0 && nums[n - 1] == nums[0]) n --;这一步不要忘记了，我错了。。。。
        int l = 0, r = n - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[r]) r = mid;//说明右边递增，突变区间在左边。
            else l = mid + 1;
        }
        return nums[l];
    }
};