Как найти максимальный элемент в отсортированном и повернутом массиве с кодом ниже?

Question

Я знаю, что есть много решений, чтобы найти максимум в отсортированном повернутом массиве. Но ниже мой код, и я хочу изменить этот код для работы на всех входных данных. Прямо сейчас в нескольких случаях это не работает.

Помогите мне найти ошибку. если какие-либо изменения требуются, то дайте мне знать.

#arr is the list of elements
#length is the length of the list
#left,right and mid indicates the different positions of the array 

def find_max(arr,length):
    left=0
    right=length-1

    while left<right :
            if right-left==1 :
                    return max(arr[left],arr[right]) 

            mid=(left+right)>>1

            if arr[mid]>arr[right]:
                    left=mid
            else:
                    right=mid-1

    return arr[left]

Этот код не работает для следующих выводов: arr = [5, 6, 7, 1, 2, 3, 4]

Для этого выхода 5пока должно быть 7.

Answer 1

Ваш переключатель if переместится в ту сторону (else), когда подрешетка (между left и right включительно) полностью поднимется. Поэтому вы должны проверить этот конкретный сценарий тоже.

Это вы делаете с дополнительным условием в вашем if:

if arr[mid] > arr[right] or arr[left] < arr[right]:

Если первое условие ложно, то мы знаем, что arr[mid] < arr[right],Тогда, если также arr[left] < arr[right], мы можем сделать вывод, что также arr[left] < arr[right] (если нет, то это не повернутый отсортированный список). И это означает, что подмассив полностью возрастает, а arr[right] является наибольшим значением.

Таким образом, вы можете дополнительно оптимизировать и сразу выйти в этом случае:

if arr[mid] > arr[right]:
    left = mid
elif arr[left] < arr[right]:
    return arr[right]
else:
    right = mid-1

Каксломать его

Есть только три способа, которыми можно заказать arr[left], arr[mid], arr[right]:

1. arr[left] < arr[mid] < arr[right]: максимальное значениеэто arr[right]

2. arr[mid] < arr[right] < arr[left]: максимальное значение находится слева mid

3. arr[right] < arr[left] < arr[mid]: максимальноезначение справа от mid.

Любой другой порядок нарушит условие, что список является повернутым, отсортированным списком.

Answer 2

я наконец нашел ответ с помощью Trincot . Здесь я публикую ответ для всех, кто будет искать его в будущем.

def find_max(arr,length):
left=0
right=length-1

while left<right :
        if arr[left] < arr[right]:
                return arr[right] 

        mid=(left+right)>>1

        if arr[mid]>arr[right]:
                left=mid
        else:
                right=mid-1

return arr[left]

:)