30

I recently started looking at MIT's 6.006 lectures and in the first lecture the instructor presented peak-finding algorithm.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

According to his definitions:

Given an array [a,b,c,d,e,f,g] where a-g are numbers, b is a peak if and only if a <= b and b>= c.

He gave a recursive approach:

if a[n/2] < a[n/2 -1] then look for a peak from a[1] ... a[n/2 -1]
else if a[n/2] < a[n/2+1] then look for a peak from a[n/2+1] ... a[n]
else a[n/2] is a peak

He said the algorithm is T(n) = T(n/2) + o(1) = o(lgn)

In his pdf he also gave a complete example: [6,7,4,3,2,1,4,5]

Both 7 and 5 are peaks. But doesn't the algorithm above only finds 7 as peak just because the middle element happens to satisfy the first branch?

  1. So if we were supposed to find all the peaks, would we still be walking through the entire array? Would it mean worst case N?

  2. Does his definition implies we just need to find a single peak?

I believe this problem can be viewed as finding the maximum and minimum element in Riverst's Introduction to Algorithm book.

CppLearner
  • 16,273
  • 32
  • 108
  • 163

5 Answers5

34

Yes, this algorithm only finds a single peak.

If you want to find all the peaks you have to check all the elements, so it's going to be O(n).

Note: a peak is not necessarily a global maximum.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
8

I am not quite convinced if this algorithm is the best way to find an interesting peak. It tends to favor the comparison at middle element which might drive the search to suboptimal direction and eventually the algorithm would always end up in finding peak at Edges and not in the middle. Simple example

[1,2,3,4,5,6,7,8] => Peak would be 8

[6,21,7,8,9,10,11,13] => Peak would be 13 while peak of 21 is more interesting

sure, the algorithm is guaranteed to find a peak because it moves in higher direction but as I show in the example, the peak may not be the interesting one!

aagosh
  • 109
  • 1
  • 3
  • 12
    Define "interesting" – John Chang Apr 10 '17 at 15:34
  • I think the author means that the most interesting peak is the one with the maximum difference with its neighbors (possibly, the mean difference) i.e. `max( a[i] - (a[i-1] - a[i+1]) / 2 )`. – LRDPRDX Feb 18 '21 at 07:24
  • Here is a [better description of the problem](https://leetcode.com/problems/find-peak-element/) – Song Wang Apr 06 '21 at 22:31
5

I just started this course yesterday, and the problem statement is:

Problem: Find a peak if it exists (Does it always exist?)

So, what the algorithm does is just trying to find a peak, the first one available, in the least time possible.

That's why this algorithm finds only a single peak.

Nathan
  • 2,705
  • 23
  • 28
0

This algorithm looks quite similar to binary search algorithm. Binary search works only on sorted arrays, and this peak-searching algorithm looks like it is supposed to work with another definition: x[p] is a peak if for 0 <= i < p x[i] <= x[i + 1] and for p <= i < x.size x[i] >= x[i + 1]. If we decide that the definition in the question is wrong, and this one is right: everything is OK. And it looks like it is wrong, because it gives several peaks in the second case, you are right.

haskile
  • 48
  • 4
0

I recently started studying that too and here is what I found out: A 1D array element is a peak if it is NOT smaller than its neighbors and for a sorted array, the last element is always the peak and the solution provided in the course is quite similar to how binary search works using divide and conquer and also the question also says find a single peak, we can have multiple peaks but we need the first peak element and we are done.

For instance we have 1D array of length n:

    DO:
    m = n/2
    neigborLeft = m-1
    neigborRight = m+1
    if neigborLeft >= 0 && a[neigborLeft] > a[m] 
       //recursion with left elements
    else if neigborRight <= n-1 && a[neigborRight] > a[m] 
        //recursion with right elements
     else
       // peak value is a[m]

Read more: geeksforgeeks.org/find-a-peak-in-a-given-array/

dejavu
  • 13
  • 6