首页 > 代码库 > LeetCode "Find Minimum in Rotated Sorted Array II"

LeetCode "Find Minimum in Rotated Sorted Array II"

Similar with version I, but analysis is different. With the possibility of duplication, only ">" indicate a definite case of next search space.

class Solution {public:        int _findMin(vector<int> &num, int s, int e)    {        if (s == e) return num[s];        if ((s + 1) == e)    return std::min(num[s], num[e]); // assumption on input                int mid = s + ((e - s) >> 1);        int a = num[s], b = num[mid], c = num[mid + 1], d = num[e];                if (a > b) return _findMin(num, s, mid);        if (c > d) return _findMin(num, mid + 1, e);        if (b > c) return c;                return std::min(_findMin(num, s, mid), _findMin(num, mid + 1, e));    }    int findMin(vector<int> &num)     {        return _findMin(num, 0, num.size() - 1);    }};

LeetCode "Find Minimum in Rotated Sorted Array II"