寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]

若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

示例:

输入：nums = [1,3,5]
输出：1
  

思路

解法一：

与153. 寻找旋转排序数组中的最小值不同之处在于数组元素可能是重复的。

中间数与右边界比较

当中间数比右边界表示的数大的时候，中间数一定不是目标数（旋转排序数组的最小值）。

举个例子：

例 3：[7, 8, 9, 10, 11, 12, 1, 2, 3]

中间数 11 比右边界 3 大，因此「中间数」以及「中间数左边的数」一定不存在旋转排序数组的最小值，下一轮搜索的区间是 [mid + 1..right]，因此 left = mid + 1。

当中间数比右边界表示的数小的时候，中间数就可能是目标数（旋转排序数组的最小值）。

举个例子：

例 4：[7, 8, 1, 2, 3]

中间数 1 比右边界表示的数小的时候，说明，中间数到右边界是递增的（对于这道题是非递减），那么中间数右边的（不包括中间数）就一定不是目标数，可以把它们排除，不过中间数有可能是目标数，就如本例，因此，把右边界设置为 right = mid。

当中间数与右边界表示的数相等的时候，看下面两个例子：

例 5：[0, 1, 1, 1, 1, 1, 1]

例 6：[1, 1, 1, 1, 0, 1, 1]

目标值可能在中间数的左边，也可能在中间数的右边，那么该怎么办呢？很简单，此时你看到的是右边界，就把只右边界排除掉就好了。正是因为右边界和中间数相等，你去掉了右边界，中间数还在，就让中间数在后面的循环中被发现吧。

因此，根据中间数和右边界的大小关系，可以使用二分法搜索到目标值。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]
  