算法:在一条线上找到峰值

Question

给定 n 个整数，排列成一行，展示一种可以找到一个峰的高效算法。峰值是一个数字，它不小于它旁边的两个数字(或者它旁边的一个数字，如果它在行的末尾。)

Answer 1

O(log n) 算法存在。我们使用分而治之。

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]