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.

follow up,和一主要的不同在于有重复数字。当

class Solution(object):    def findMin(self, nums):        """        :type nums: List[int]        :rtype: int        """        if not nums:            return 0        l = 0        r = len(nums) - 1                while l + 1 < r:            mid = l + (r - l)/2            if nums[mid] == nums[r]:  ＃只用移动一位就可以。                r -= 1            elif nums[mid] > nums[r]:                l = mid            else:                r = mid            return min(nums[l], nums[r])