[LintCode] Find Minimum in Rotated Sorted Array II

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.

The array may contain duplicates.

Example

Given [4,4,5,6,7,0,1,2] return 0

class Solution {
public:
    /**
     * @param num: the rotated sorted array
     * @return: the minimum number in the array
     */
    int findMin(vector<int> &num) {
        // write your code here
        int end = num.size() - 1;
        int start = 0;
        while(start < end)
        {
            while(start+1<end && num[start] == num[start+1]) start++;
            while(end-1>start && num[end] == num[end-1]) end--;

            int mid = (start+end)/2;
            if(num[mid] > num[end]) start = mid + 1;
            else end = mid;
        }
        
        return num[start];
    }
};