Search code examples
divide-and-conquer

Divide and Conquer Method for peakFinder

The Divide and Conquer method for finding a peak works a lot like this

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]

So my Question is if we use this algorithm we may loose the other half where the peak may actually exist

Or are we assuming that the peak we find is one peak and the one in the other half is another therefore there might be Two peaks in a single array

Solution

  • I'll use this as peak definition "An array element is peak if it is NOT smaller than its neighbors."

    This array has 2 peak elemets:

    [10, 20, 15, 2, 23, 90, 67]

    20 and 90

    The algorithm posted above would would only return one value. Not all peak values, not even the biggest peak value - it simply finds some peak value.