题解 | #旋转数组的最小数字#

时间复杂度要求O(lgn)，考虑二分法：

1. 如果当前数组 v[l] < v[j]，则当前数组是有序的，返回最小值v[l]；
2. 否则取数组中间mid：
   1. 如果v[l] < v[mid],则最小值在mid + 1 ~ r 中；
   2. 如果v[l] > v[mid],则最小值在l ~ mid 中； 3.如果v[l] == v[mid],则取l ~ mid 和mid + 1 ~ r 中的min。

注意：

1. 如果数组中的两个元素i <j且v[i] < v[j], 则v[i]~v[j]间是有序的
2. 二分法的迭代最好是Sl∪Sr=S，Sl∩Sr=∅(l ~ mid 和mid + 1 ~ r )，这样保证了用l == r跳出去。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        return takeMid(rotateArray, 0, rotateArray.size() - 1);
    }
    
    int takeMid(vector<int> rotateArray, int l, int r){
        if(l == r || rotateArray[l] < rotateArray[r])
            return rotateArray[l];
        int mid = (l + r) / 2;
        if(rotateArray[l] > rotateArray[mid])
            return takeMid(rotateArray, l, mid);
        else if(rotateArray[l] < rotateArray [mid])
            return takeMid(rotateArray, mid + 1, r);
        else
            return min(takeMid(rotateArray, l, mid),takeMid(rotateArray, mid + 1, r));
    }
};