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"

推荐阅读