algorithm - 分治算法用于在数组中查找峰值。

Question

对于数组 a：a ₁ , a ₂ , ... a _k , ... a _n ，当且仅当 a _k-1 ≤ a _k ≥ a _k+1当 1 < k 且 k < n 时， a _{k是一个峰值。}如果a ₁ ≥ a ₂，a 1_是一个峰，如果a _n-1 ≤ a _{n ，a n}是一个峰。目标是从阵列中找到一个峰。

分治算法如下：

find_peak(a,low,high):
    mid = (low+high)/2
    if a[mid-1] <= a[mid] >= a[mid+1] return mid // this is a peak;
    if a[mid] < a[mid-1] 
        return find_peak(a,low,mid-1) // a peak must exist in A[low..mid-1]
    if a[mid] < a[mid+1]
        return find_peak(a,mid+1,high) // a peak must exist in A[mid+1..high]

为什么这个算法是正确的？我认为它可能会因丢失存在峰值的阵列的一半而受到影响。

Answer 1

该算法是正确的，尽管它需要一些微积分来证明。第一种情况是微不足道的→峰值。第二种情况是“半峰”，这意味着它有下坡，但没有上坡。

我们这里有两种可能性：

• 该函数单调递减，直到_中间→ a ₁ ≥ a ₂为峰值。
• 该函数不是单调递减的，直到 a _mid → 存在 1≥k≥mid，其中 a _k ≥ a _k-1。让我们选择这个陈述成立的最大 k → a _k+1 < a _k ≥ a _k-1 → 这就是峰值。

类似的论点可以应用于具有相反“半峰”的第三种情况。