algorithm - アルゴリズム: ライン内のピークを見つける

Question

行に配置された与えられnた整数は、1 つのピークを見つけることができる効率的なアルゴリズムを示しています。ピークとは、その隣の 2 つの数字 (または行末にある場合は、その隣の 1 つの数字) 以上の数字です。

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]