Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

10/10/2015 udpate

An iterative approach

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]){
                right = mid;
            }
            else if(nums[mid] > nums[right]){
                left = mid + 1;
            }
            else{
                right = right - 1;
            }
        }
        return nums[left];
    }
};

//How big will the input array be?
//Will the element be negative?
//If duplicated are allowed, the worst case would be o(n)

class Solution {
public:
    int findMin(vector<int>& nums) {
        return _findMin(nums, 0, nums.size());
    }
    
    //[start, end)
    int _findMin(vector<int>& nums, int start, int end){
        //base condition
        if(end - start == 1){
            return nums[start];
        }
        //worst condition
        else if(nums[start] == nums[end - 1]){
            int mid = (start + end) / 2;
            return min(_findMin(nums, start, mid), _findMin(nums, mid, end));
        }
        //ordinary case
        else{
            int mid = (start + end) / 2;
            if(nums[start] < nums[end - 1]){
                //pivot is not in [start, end)
                return nums[start];
            }
            else{
                //pivot is in [start, end)
                //nums[start] > nums[end - 1]
                if(nums[mid] >= nums[start]){
                    return _findMin(nums, mid + 1, end);
                }
                else{
                    return _findMin(nums, start + 1, mid + 1);//BUG: change start to start + 1.
                    //since numns[start] is bigger than nums[mid], so start can't be the result.
                }
            }
        }
    }
};