求旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。要求：输入一个 非递减 排序的数组的一个旋转，输出其最小元素。如：数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

• case 1：3 4 5 6 7 1 2 左侧为顺序，则目标在右侧 [mid+1, r]
• case 2：6 7 1 2 3 4 5 右侧为顺序，则目标在左侧 [l, mid]
• case 3：1 0 1 1 1 1 1 未知顺序，只能遍历 [l+1, r]

迭代式：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        vector<int>& a = rotateArray;
        if(a.empty()) return 0;

        int l(0), r(a.size()-1), mid(0);
        while(l<r){
            mid = (l+r) >> 1;
            if(a[l] < a[r]) return a[l];  // 提前退出
            else if(a[l] < a[mid]) l = mid+1;  // 3 4 5 1 2
            else if(a[mid] < a[r]) r = mid;    // 4 5 1 2 3 
            else l++;  // 避免1101111等情况
        }
        return a[l];
    }
};

递归式：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.empty()) return 0;
        return find(rotateArray, 0, rotateArray.size()-1);
    }

    int find(vector<int>& a, int l, int r){
        if(l==r or a[l]<a[r]) return a[l];
        int mid = (l+r) >> 2;
        if(a[l] < a[mid])  return find(a, mid+1, r);
        else if(a[mid] < a[r])  return find(a, l, mid);
        else return find(a, l+1, r);  // 避免1101111等情况
    }
};