Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:


	[4,5,6,7,0,1,4] if it was rotated 4 times.
	[0,1,4,4,5,6,7] if it was rotated 7 times.


Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

&nbsp;
Example 1:
Input: nums = [1,3,5]
Output: 1
Example 2:
Input: nums = [2,2,2,0,1]
Output: 0

&nbsp;
Constraints:


	n == nums.length
	1 &lt;= n &lt;= 5000
	-5000 &lt;= nums[i] &lt;= 5000
	nums is sorted and rotated between 1 and n times.


&nbsp;
Follow up: This problem is similar to&nbsp;Find Minimum in Rotated Sorted Array, but&nbsp;nums may contain duplicates. Would this affect the runtime complexity? How and why?

&nbsp;

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return min(nums)
        
class Solution {
    public int findMin(int[] nums) {
        int l = 0;
        int h = nums.length - 1;
        while (l < h) {
            while (l < h && nums[l] == nums[l + 1])
                ++l;
            while (l < h && nums[h] == nums[h - 1])
                --h;
            int mid = l + (h - l) / 2;
            if (nums[mid] > nums[h]) { // smaller elements are in the right side
                l = mid + 1;
            } else {
                h = mid;
            }
        }
        return nums[l];
    }
}
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=0,h=nums.size()-1;
        while(l<h){
            int m=l+(h-l)/2;
            if(nums[m]<nums[h]) h=m;
            else if(nums[m]>nums[h]) l=m+1;
            else h--;
        }
        return nums[h];
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let min = Infinity;
    let l = 0;
    let r = nums.length - 1;
    while (l <= r) {
        const m = Math.floor((l + r) / 2);

        // Eliminate dupes ......................... only difference from #153
        while (l < m && nums[l] === nums[m]) l++;
        while (r > m && nums[r] === nums[m]) r--;
        // .........................................

        // locate the sorted side, the opposite side has the break point
        // min should be on the side that has the break point, so continue search on that side
        if (nums[l] <= nums[m]) {
            // left side is sorted (or l & m are the same index)
            // brake is on right side
            min = Math.min(min, nums[l]);
            l = m + 1;
        } else {
            // right side is sorted
            // break is on left side
            min = Math.min(min, nums[m]);
            r = m - 1;
        }
    }
    return min;
};
Find Minimum in Rotated Sorted Array II