Поиск минимума в списке, который уменьшается, а затем увеличивается и может содержать дубликаты

Question

Учитывая список, который можно разбить на две части: L[:z] и L[z:], так что первая не увеличивается, а вторая не уменьшается и может содержать или не содержать дублирующиеся элементы, создайте функцию так, чтобы:

---

Входные данные :

• Список L, как указано выше
• Значение k, которое представляет максимальное количество повторений любого данного значения в списке

Выход:

• Минимальное значение списка

Сложность и требования

• O(log n)
• Можно использовать только встроенные функции библиотеки, не включая мин / макс

---

У меня есть следующее:

def findmin(L, k = None):
    left = 0
    right = len(L)-1
    foundmin = False

    while not foundmin:
        mp = (left + right)//2
        if L[mp] > L[mp+1]:
            left = mp
        elif L[mp-1] < L[mp]:
            right = mp+1
        else:
            return L[mp]

Это работает только для некоторых списков, таких как: L = [9,9,4,3,2,1,7,7,10,10]

Но это не работает правильно для списков, таких как: L = [6,5,4,3,3,3,3,3,3,3,3,3,1,7,7,7,7]

Я попытался изменить функцию, чтобы приспособить повторяющиеся элементы безрезультатно. Я также не вижу полезности ввода k для функции. Мысли?

Answer 1

Этот код работает в O(logn) и не использует k параметр.

Это какой-то бинарный поиск, например, @coldspeed.

def find_min(l, k=None):
    left = 0
    right = len(l) - 1
    while left <= right:
        middle = (left + right) // 2
        if l[middle] < l[left] or (l[middle] == l[left] and middle > left):
            left = middle
        elif l[middle] < l[right] or (l[middle] == l[right] and middle < right):
            right = middle
        else:
            return l[middle]

Answer 2

Проблема с вашим решением состоит в том, что если числа по обе стороны от mp равны mp, то ваш алгоритм выдаст L[mp]. Таким образом, во втором случае он выдает 3. Простой вещью будет проверка следующего неравного числа вместо проверки только соседних.

Модифицированное решение:

def findmin(L, k = None):
    left = 0
    right = len(L)-1
    foundmin = False

    while left<right:
        print(left, right)
        mp = (left + right)//2
        next_diff = mp+1
        while(next_diff < len(L)-1 and L[next_diff] == L[mp]):
            next_diff+=1
        if L[mp] > L[next_diff]:
            left = next_diff
        elif L[mp] <= L[next_diff]:
            right = mp
    return L[left]

PS: хотя сложность в этом случае становится O(k* log n).