Algorithmus: Finde den Peak in einer Linie

Question

Gegeben n Ganzzahlen, die in einer Linie angeordnet sind, zeigen Sie einen effizienten Algorithmus, der einen Gipfel finden kann. Ein Gipfel ist eine Zahl, die nicht kleiner ist als die beiden Zahlen neben ihr (oder die eine Zahl neben ihr, wenn sie am Ende der Linie steht.)

Answer 1

Es gibt einen O(log n) Algorithmus. Wir verwenden Teile und Herrsche.

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) // Es muss ein Peak in A[1..mid-1] existieren
  if A[mid] < A[mid+1]
    return find_peak(mid+1,hi) // Es muss ein Peak in A[mid+1..hi] existieren