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 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.

Solution: Binary Search

When duplicates are allowed, we need to handle the situation where left and right is equal. In this case, we only update the right index.

int findMin(vector<int>& nums) {        
    int left = 0, right = nums.size()-1;
    while (left < right) {
        int mid = left + (right - left)/2;

        if (nums[left] == nums[right]) {
            right -= 1;
        } else if (nums[left] < nums[right]) {
            return nums[left];
        } else if (nums[left] <= nums[mid]) {
            left = mid+1;
        } else {
            right = mid;
        }
    }

    return nums[left];
}

int findMin(vector<int>& nums) {        
    int left = 0, right = nums.size()-1;
    while (left < right) {
        int mid = left + (right - left)/2;
        if (nums[mid] > nums[right]) {
            // Left half is sorted
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            // Right half is sorted
            right = mid;
        } else {
            // If mid is equal to right
            right -= 1;
        }
    }

    return nums[left];
}