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

Question

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

---

Ввод:

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

Вывод:

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

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

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

---

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

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).