Минимум во вращаемом отсортированном массиве с дубликатами

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 дубликатов), тогда был бы полезен двоичный поиск.