分而治之找到一个高峰阵列应用的算法。 [英] Divide and conquer algorithm applied in finding a peak in an array.

问题描述

对于数组A：<子> 1 ，一个 ₂ ，＆hellip;一个<子> K ，＆hellip;一个<子> N ，一个<子> K 是一个高峰，当且仅当<子> K-1 和乐;一个<子> K ＆GE;一个<子> K + 1 时1 LT; K和K＆其中; ñ。一个<子> 1 是一个高峰，如果<子> 1 ＆GE;一个 ₂ 和<子> N 是一个高峰，如果<子> N-1 和乐;一个<子> N 。的目标是找到从阵列一个峰。

For an array a: a₁, a₂, … a_k, … a_n, a_k is a peak if and only if a_k-1 ≤ a_k ≥ a_k+1 when 1 < k and k < n. a₁ is a peak if a₁ ≥ a₂, and a_n is a peak if a_n-1 ≤ a_n. The goal is to find one peak from the array.

一个分而治之算法，给出如下：

A divide and conquer algorithm is given as follows:

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]

为什么这个算法是正确的？我觉得可能遭受损失的一半，其中存在一个峰值的数组。

Why this algorithm is correct? I think it may suffer from losing half of the array in which a peak exists.

推荐答案

该算法是正确的，虽然它需要一点微积分的证明。 第一种情况是琐碎和RARR;峰。 第二种情况是一个半峰，意思是它具有向下斜坡，而不是向上。

The algorithm is correct, although it requires a bit of calculus to prove. First case is trivial → peak. Second case is a "half peak", meaning that it has the down slope, but not up.

我们有两个可能的选择：

We have 2 possibilities here:

• 在该函数单调递减，直到一个<子>中＆RARR;一个<子> 1 ≥一个 ₂ 的高峰。
• 的功能并不单调递减的，直到一个<子>中＆RARR;有一个1≥k≥mid，对于其中<子> K ≥一个<子> K-1 。让我们选择的这这种说法是真RARR最大的K表;一个<子> K + 1 ＆LT;一个<子> K ≥一个<子> K-1 ＆RARR;这就是峰值。

• The function is monotonically decreasing till a_mid → a₁ ≥ a₂ is the peak.
• The function is not monotonically decreasing till a_mid → There is a 1≥k≥mid, for which a_k ≥ a_k-1. Let's choose the largest k for which this statement is true → a_k+1 < a_k ≥ a_k-1 → and that's the peak.

类似的参数可以应用于第三种情况与对面的半峰。

Similar argument can be applied for the third case with the opposite "half peak".

这篇关于分而治之找到一个高峰阵列应用的算法。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！