求数组局部大值

在海城等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站设计、网站建设 网站设计制作按需定制开发,公司网站建设,企业网站建设,成都品牌网站建设,网络营销推广,外贸网站制作,海城网站建设费用合理。

给定一个无重复元素的数组A[0…N-1]，求找到一个该数组的局部大值。规定：在数组边界外的值无穷小。即：A[0]＞A[-1]，A[N-1] ＞A[N]。

显然，遍历一遍可以找到全局大值，而全局大值显然是局部大值。

可否有更快的办法？

算法描述

使用索引left、right分别指向数组首尾。

求中点 mid = ( left + right ) / 2

A[mid]＞A[mid+1]，丢弃后半段：right=mid

A[mid+1]＞A[mid]，丢弃前半段：left=mid+1

递归直至left==right

时间复杂度为O(logN)。

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)

网站栏目：Python求数组局部最大值的实例-创新互联
网站路径：http://scyanting.com/article/jogoi.html