原题

假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。

你需要找到其中最小的元素。
数组中可能存在重复的元素。
给出[4,4,5,6,7,0,1,2] 返回 0

解题思路

• 与[Find Minimum in Rotated Sorted Array I]相比，本题中有重复元素，还是让nums[mid]和nums[end]比较，但要考虑nums[mid] == mums[end]的情况，此时 end -= 1
• 极端情况[1, 2, 2, 2, .....2]，nums[mid]和mums[end]一直相等，操作一直是end -= 1，所以时间复杂度变成O(n)
• 所以方法二就是直接遍历一遍，维护一个最小值
• 对于方法一，还可以想成在普通的binary search基础上，加入两个while循环

while start + 1 < end:
    mid = start + (end - start) / 2
    # 如果重复，start向后移动
    while nums[mid] == nums[start] and start < mid:
        start += 1
    # 如果重复，end向前移动
    while nums[mid] == nums[end] and end > mid:
        end -= 1
    if nums[mid] > nums[end]:
        start = mid
    elif nums[mid] < nums[end]:
        end = mid

完整代码

# 方法一
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
            
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[end]:
                start = mid
            elif nums[mid] < nums[end]:
                end = mid
            else:
                end -= 1
        return min(nums[start], nums[end])

# 方法二
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return
        min = nums[0]
        for item in nums:
            if item < min:
                min = item
        return min