Python 实现数组局部最大值查找算法

数组局部最大值查找

数组局部最大值查找

假设存在一个不含重复元素的数组 A[0…N-1]，目标是找出其中的一个局部最大值。根据定义，数组边界之外的值视为负无穷大，即满足 A[0] > A[-1] 且 A[N-1] > A[N] 的条件。

直观上，遍历整个数组可以找到全局最大值，而全局最大值必然也是局部最大值。

是否存在比遍历更快的解决方案？

算法描述

算法描述

定义两个指针 left 和 right，分别指向数组的起始位置和结束位置。

计算中间索引 mid，公式为 mid = (left + right) / 2。

若 A[mid] > A[mid+1]，说明局部最大值位于左半部分（含 mid），此时更新 right = mid。

若 A[mid+1] > A[mid]，说明局部最大值位于右半部分（不含 mid），此时更新 left = mid + 1。

重复上述步骤，直到 left 等于 right，此时即为找到的局部最大值索引。

该算法的时间复杂度为 O(logN)。

Python 代码实现

Python 代码实现

def local_maximum(li):
  if li is None:
    return
  left = 0
  right = len(li) - 1
  while left < right:
    mid = int((left + right) / 2)
    if li[mid] > li[mid + 1]:
      right = mid
    else:
      left = mid + 1
  return li[left]


if __name__ == '__main__':
  li = [1, 5, 2, 3, 4, 0]
  result = local_maximum(li)
  print(result)

运行输出结果为：4

以上就是 Python 查找数组局部最大值的完整实现。希望本文内容能为您提供帮助，欢迎收藏并支持本站获取更多技术分享。