154 Find Minimum in Rotated Sorted Array II¶

Suppose an array sorted in ascending order 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.

The array may contain duplicates.

**Idea: **

Divide and conquer

Time complexity:

Average: O(logn) Worst: O(n)

Solution¶

class Solution {
public:
    int findMin(vector<int> &num) {
        return findMin(num, 0, num.size()-1);
    }

    int findMin(const vector<int>& num, int l, int r)
    {
        // One or two elements, solve it directly
        if (l+1 >= r) return
            min(num[l], num[r]);

        // Sorted
        if (num[l] < num[r])
            return num[l];

        int m = l + (r-l)/2;

        // Recursively find the solution
        return min(findMin(num, l, m - 1),
                   findMin(num, m, r));
    }
};