Catalogue: array-分治法搜索

Question

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

class Solution {public:    int findMin(vector<int> &num) {        ret = 0;        binarySearch(num,0,num.size()-1);        return num[ret];    }        void binarySearch(vector<int> &num, int start, int end)    {        if(end-start<=1)        {            if(num[end]>num[start]) return;            else            {                ret = end;                return;            }        }                int mid = (start + end) >> 1;        if(num[start]>num[mid])          binarySearch(num, start, mid);        else if(num[mid+1]>num[end])          binarySearch(num, mid+1, end);        else if(num[mid]>num[mid+1])          ret = mid+1;    }private:    int ret;};

Find Minimum in Rotated Sorted Array