溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
求數組局部最大值
給定一個無重復元素的數組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 求數組局部最大值的實例就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
