求數組局部最大值

給定一個無重復元素的數組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)

輸出結果：4

以上這篇Python 求數組局部最大值的實例就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持武林網之家。