如何使用以下代码在排序和旋转数组中找到最大元素？

Question

我知道有很多解决方案可以在排序的旋转数组中找到最大值。但下面是我的代码，我想修改这些代码以处理所有输入。现在在少数情况下，它不起作用。

帮我找出bug。如果需要任何修改，请告诉我。

#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

当子数组（在 left 和 right 之间）完全升序时，您的 if 开关将转到错误的一侧（else）。所以你也应该检查那个特定的场景。

这需要在 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]只有三种订购方式：

arr[left] < arr[mid] < arr[right]：最大值为arr[right]
arr[mid] < arr[right] < arr[left]：最大值在mid
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]

:)

如何使用以下代码在排序和旋转数组中找到最大元素？

how to find the maximum element in sorted and rotated array with the below code?

sorting

algorithm

binary-search

python-3.x

如何分解