Peak finding algorithm MIT OCW 6.006 - Does it always exist?

Question

This week I started MIT OCW 6.006 lectures and in the first lecture the professor introduced 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:

[a b c d e f g h i]
1 2 3 4 5 6 7 8 9
a-i are numbers

Position 2 is a peak if and only if b ≥ a and b ≥ c. Position 9 is a peak if i ≥ h

He proposes this algorithm to improve its complexity:

If a[n/2] < a[n/2 − 1] then only look at left half 1 . . . n/2 − − − 1 to look for peak
• Else if a[n/2] < a[n/2 + 1] then only look at right half n/2 + 1 . . . n to look for peak
• Else n/2 position is a peak: WHY?
    a[n/2] ≥ a[n/2 − 1]
    a[n/2] ≥ a[n/2 + 1]

However, what if I have this example array:

[9,8,7,6,5,2,3,1]

The algorithm would work like this:

Step 1: a[n/2] < a[n/2-1]? --> 6 < 7? --> yes, look at left half [9,8,7,6]
Step 2: a[n/2] < a[n/2-1]? --> 8 < 9? --> yes, look at left half [9,8]
Step 3: ???

No peak would be found, although there is a peak: [9,8,7,6,5,2,3,1]

I guess I am missing something, but i didn't figure out. Someone can explain me why it is not working?

I found this related question, but no answer: Peak finding algorithm

The peak is 9 in your example. The algorithm assumes that there is a single peak. — user3386109, Jan 09 '20 at 20:46
He assumes only the tail can be a peak. "Position 2 is a peak if and only if b ≥ a and b ≥ c. Position 9 is a peak if i ≥ h". He doesn't say "Position 1 is a peak if a ≥ b". — Diogo Bratti, Jan 09 '20 at 20:57
Yes, but I think that's just an oversight. The algorithm is checking the slope, and moving in the direction of increasing values. So it will find a peak at either end of the array. — user3386109, Jan 09 '20 at 21:22
The algorithm *does* seem to have a problem with arrays like [1,2,2,2,2,3] since it will declare that 2 is a peak, when it isn't. — user3386109, Jan 09 '20 at 21:24

score 0 · Answer 1 · edited Mar 14 '20 at 05:57

You have to consider boundary condition by yourself.
Here Is complete Steps:

Step 1: a[n/2] < a[n/2-1]? --> 6 < 7? --> yes, look at left half [9,8,7,6]
Step 2: a[n/2] < a[n/2-1]? --> 8 < 9? --> yes, look at left half [9,8]
Step 3: ??? <br>
//if you put a check on boundary condition then
Step 3: a[n/2] > a[n/2+1]? --> 9 > 8? --> yes, look at right half [8]
Step 4: loop terminates as only one element is left(it is a peak)

You can found a better description of problem here.

Peak finding algorithm MIT OCW 6.006 - Does it always exist?

1 Answers1