具有重复项的旋转排序数组中的最小值

Question

我正在尝试在具有重复项的旋转排序数组中找到最小值：

我尝试过：

def find_pivot(arr):
    lo = 0 
    hi = len(arr) -1 
    while lo<=hi:
        mid = (hi+lo)//2 
        if arr[mid]<arr[0]:
            hi = mid-1
        else:
            lo = mid+1
    return lo 


class Solution:
    """
    @param nums: a rotated sorted array
    @return: the minimum number in the array
    """
    def findMin(self, nums):
        pivot_index = find_pivot(nums)
        left = nums[:pivot_index]
        right = nums[pivot_index:]
        if right:
            return right[0]
        return left[0]

当数组为[999,999,1000,1000,10000,0,999,999,999]时，此操作失败。我的算法返回999，应该返回0

我该如何解决？

Answer 1

由于重复，二进制搜索在这里不起作用。

假设您的数组是[1,1,1,1,1,0,1,1]。然后arr[lo] = arr[hi] = arr[mid] = 1：您将潜入哪一半？您可能会说“对的！”当然可以，但是为什么呢？仅拥有这三个项目的所有信息不足以使您确定自己的选择。实际上，该数组可能是[1,0,1,1,1,1,1,1]，但仍然是arr[lo] = arr[hi] = arr[mid] = 1，但枢轴现在不在右半部分。

在最坏的情况下，对于这种类型的实例，您仍然需要扫描整个阵列。

如果数组中的顺序更严格，这意味着没有重复项（或不超过k个重复项，那么二进制搜索将很有用。