Python 求數(shù)組局部最大值的實(shí)例
更新時(shí)間：2019年11月26日 15:55:50 作者：RealEmperor
今天小編就為大家分享一篇Python 求數(shù)組局部最大值的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
求數(shù)組局部最大值
給定一個(gè)無重復(fù)元素的數(shù)組A[0…N-1]，求找到一個(gè)該數(shù)組的局部最大值。規(guī)定：在數(shù)組邊界外的值無窮小。即：A[0]＞A[-1]，A[N-1] ＞A[N]。
顯然，遍歷一遍可以找到全局最大值，而全局最大值顯然是局部最大值。
可否有更快的辦法？
算法描述
使用索引left、right分別指向數(shù)組首尾。
求中點(diǎn) mid = ( left + right ) / 2
A[mid]＞A[mid+1]，丟棄后半段：right=mid
A[mid+1]＞A[mid]，丟棄前半段：left=mid+1
遞歸直至left==right
時(shí)間復(fù)雜度為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)
輸出結(jié)果：4
以上這篇Python 求數(shù)組局部最大值的實(shí)例就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
您可能感興趣的文章:
相關(guān)文章
python中使用PIL制作并驗(yàn)證圖片驗(yàn)證碼
本篇文章給大家分享了python中使用PIL制作并驗(yàn)證圖片驗(yàn)證碼的具體代碼以及說明，需要的朋友參考下吧。2018-03-03
這篇文章主要介紹了Python爬蟲谷歌Chrome F12抓包過程原理解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06
本文主要介紹了Python一鍵生成所有依賴包清單方法小結(jié)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要介紹了python使用sessions模擬登錄淘寶的方式，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-08-08
Python 中的 global 標(biāo)識對變量作用域的影響
global 標(biāo)識用于在函數(shù)內(nèi)部，修改全局變量的值。這篇文章主要介紹了Python 的 global 標(biāo)識對變量作用域的影響,需要的朋友可以參考下2019-08-08
python中pyc、?pyd文件及生成使用完整實(shí)例代碼
這篇文章主要介紹了python中pyc、?pyd文件及生成使用的相關(guān)資料,重點(diǎn)講解了如何使用Python解釋器編譯.py文件為.pyc文件,以及如何使用Cython和distutils工具將C/C++代碼編譯為.pyd文件,需要的朋友可以參考下2025-04-04
使用python中的matplotlib.pyplot繪圖的時(shí)候,如果將圖片顯示出來,或者另存為圖片,常常會出現(xiàn)清晰度不夠的問題,當(dāng)然這種問題是對于png或者jpg這種格式的圖片而言的,所以本文給大家介紹了提高M(jìn)atplotlib繪圖清晰度的幾種方法,需要的朋友可以參考下2024-01-01
pycharm中代碼回滾到指定版本的兩種實(shí)現(xiàn)方法(附帶截圖展示)
在編寫代碼的時(shí)候，經(jīng)常會出現(xiàn)寫的代碼存在一些問題,但是比較難以發(fā)現(xiàn)具體存在的問題在哪里,需要將帶代碼恢復(fù)到指定的版本,下面這篇文章主要給大家介紹了關(guān)于pycharm中代碼回滾到指定版本的兩種實(shí)現(xiàn)方法,需要的朋友可以參考下2022-06-06
PyTorch中Tensor和tensor的區(qū)別及說明
這篇文章主要介紹了PyTorch中Tensor和tensor的區(qū)別及說明，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
python mongo 向數(shù)據(jù)中的數(shù)組類型新增數(shù)據(jù)操作
這篇文章主要介紹了python mongo 向數(shù)據(jù)中的數(shù)組類型新增數(shù)據(jù)操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12