算法：在一行中查找峯值

鑑於n排列成一行的整數顯示可找到一個峯值的高效算法。峯值是一個不小於其旁邊的兩個數字（或其旁邊的一個數字，如果它在該行的末尾）。算法：在一行中查找峯值

2012-10-12 Paul S.

你想要第一個高峯嗎？還是最高峯？最高峯不會是最大值嗎？ –

@CharlesBretana一個峯值就足夠了。找到最高峯需要'O（n）'。 –

爲什麼你發佈兩次[相同的問題]（http://stackoverflow.com/questions/12867018/algorithm-find-peak-in-a-circle）？ –

算法存在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]

來源

2012-10-12 21:35:45

你回答缺少退出條件。以增加序列爲例。如果lo ==你好，請回復:) :) –

@lcfseth這是真的。我想這個想法應該沒問題。 :) –

此答案無效。以序列「1 9 3 4 5 5 5」，第一個測試是數字「3 4 5」，然後算法選擇上半部分進行遞歸。上半部分沒有高峯。從未考慮下半部分的峯值。 – Skizz

算法：在一行中查找峯值

回答

相關問題