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

LeetCode "Find Minimum in Rotated Sorted Array"

There‘s usually a common strategy for "find *" problems - binary search: half the space can be dropped by some rules.

And take care of corner cases.

class Solution {    const int INVALID = std::numeric_limits<int>::min();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);        if (num[s] <= num[mid] && num[mid + 1] <= num[e])        {            if (num[mid] < num[mid + 1])            {                return num[s];            }            else            {                return num[mid + 1];            }        }        else if (num[s] <= num[mid])        {            return _findMin(num, mid + 1, e);        }        else        {            return _findMin(num, s, mid);        }        return INVALID;    }    int findMin(vector<int> &num)     {        size_t len = num.size();        return _findMin(num, 0, len - 1);    }};
View Code

 

LeetCode "Find Minimum in Rotated Sorted Array"