如何查找数组中数值停止递增开始递减的拐点索引

我们默认讨论的输入数组符合严格单峰特征：先严格递增，到最大值后严格递减，不存在数值相等的相邻元素、多峰值的情况，和你给出的示例匹配。

方法1：线性遍历（时间复杂度O(n)，适合短数组） #

• 实现逻辑：从数组第二个元素开始遍历，第一次出现当前元素小于前一个元素时，前一个元素的位置就是转折点；如果遍历完全部元素都没有出现下降（即数组全程递增），则最后一个元素就是峰值
• 示例代码（Python）：

def find_peak(arr):
    for i in range(1, len(arr)):
        if arr[i] < arr[i-1]:
            # 返回0-based索引，需要1-based索引的话此处return i即可
            return i-1
    return len(arr) - 1

• 测试验证：
  • 输入arr = [1,2,3,5,4,3,1]，返回0-based索引3，符合要求
  • 输入arr = [4,5,6,8,6,4]，返回0-based索引3，加1后得到1-based索引4，和你给出的示例结果一致

方法2：二分查找（时间复杂度O(logn)，适合长数组） #

• 实现逻辑：利用数组先增后减的有序性，每次取中间位置判断当前处于递增还是递减区间，缩小搜索范围，直到锁定峰值位置
• 示例代码（Python）：

def find_peak(arr):
    left, right = 0, len(arr)-1
    while left < right:
        mid = (left + right) // 2
        # 中间元素小于右侧，说明峰值在右半段
        if arr[mid] < arr[mid+1]:
            left = mid + 1
        # 中间元素大于右侧，说明峰值在左半段或就是mid
        else:
            right = mid
    # 返回0-based索引，需要1-based索引直接left+1即可
    return left

内容的提问来源于stack exchange，提问作者Adam Sheffield