由网友(放个屁给你追着玩)分享简介：由于 N 整数，排成一条线，显示出高效的算法，可以找到一个高峰。峰值是一个数字，是不超过两个数少它旁边（或所述一个数它旁边，如果它是在该行的末端。）Given n integers, arranged in a line, show an efficient algorithm that can find one p...

由于 N 整数，排成一条线，显示出高效的算法，可以找到一个高峰。峰值是一个数字，是不超过两个数少它旁边（或所述一个数它旁边，如果它是在该行的末端。）

Given n integers, arranged in a line, show an efficient algorithm that can find one peak. A peak is a number that is not less than the two numbers next to it (or the one number next to it, if it's at the end of the line.)

推荐答案

这是 O（log n）的算法存在。我们采用分而治之。

An O(log n) algorithm exists. We use divide-and-conquer.

find_peak(lo,hi):
  mid = (lo+hi)/2
  if A[mid] >= A[mid-1], A[mid+1] return mid
  if A[mid] < A[mid-1] 
    return find_peak(lo,mid-1) // a peak must exists in A[1..mid-1]
  if A[mid] < A[mid+1]
    return find_peak(mid+1,hi) // a peak must exists in A[mid+1..hi]