使用二分搜索在 O(log n ) 中从给定数组中查找峰值元素索引

Question

任何人都可以帮助我理解下面使用二分搜索的代码，因为给定的数组没有排序，那么我们如何找出实际的峰值元素索引？

通常它只适用于排序数组，对吗？

对于此测试用例 -

输入：arr = [0,10,5,2]

输出：1

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        h = len(arr) - 1
        while l < h:
            mid = l + (h - l) // 2
            if arr[mid] > arr[mid + 1]:
                h = mid 
            else:
                l = mid + 1
        return l

Answer 1

此代码使用二分搜索，它分为

arr[1]

和

arr[2]

。在循环中，mid 是 10，因为它大于 5

arr[mid] > arr[mid + 1]

h=1，即 10 的索引。它再次执行循环并检查 0 和 10 之间，并返回索引 10。