求數(shù)組局部大值

在海城等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶(hù)提供成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需定制開(kāi)發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),網(wǎng)絡(luò)營(yíng)銷(xiāo)推廣,外貿(mào)網(wǎng)站制作,海城網(wǎng)站建設(shè)費(fèi)用合理。

給定一個(gè)無(wú)重復(fù)元素的數(shù)組A[0…N-1]，求找到一個(gè)該數(shù)組的局部大值。規(guī)定：在數(shù)組邊界外的值無(wú)窮小。即：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)

新聞名稱(chēng)：Python求數(shù)組局部最大值的實(shí)例-創(chuàng)新互聯(lián)
鏈接URL：http://weahome.cn/article/jogoi.html