旋转数组的最小数字-递归解法

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
输入
[3,4,5,1,2]
返回值
1

解题思路

1.标签上写的是二分，示意我用二分法做。虽然二分法常用非递归做，但用递归可以更好地表达思路，而且写得快，因此本题我用递归做。
2.首先注意题干中的非递减排序，这让我联想到一条y=x直线，数组的选择就是截取直线前端一部分，平移到后面，成为一个分段线性函数。因此我们得到了几何上的直观揭示：数组的旋转即部分直线的平移。
3.接着我们要二分了，选取中点，即在分段线性函数中间砍一刀。假设最小数字在砍开的右侧，那么砍开的两侧各有什么特点？
4.左侧依然线性，右侧是分段的，各自表现为左端点<右端点，左端点>右端点.因此左端点>右端点的这侧存在最小数字。接着我们分割这侧即可。
5.和其他人不同的是，我没有拿中点的值和端点值进行比较，因为我觉得两侧端点值的关系已经能判断出最小值在哪侧了。

代码

class Solution {
public:
    int helper(vector<int> &rotateArray,int start,int end){
        if(start==end)return rotateArray[start];
        else{
            int mid = (start + end)/2;
            if(rotateArray[start]<rotateArray[end]){
                return rotateArray[start];
            }else{
                int left = helper(rotateArray,start,mid);
                int right = helper(rotateArray,mid+1,end);
                if(left>right)return right;
                else return left;
            }
        }
    }
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0)return 0;
        return helper(rotateArray, 0, rotateArray.size()-1);
    }
};