0

I came from here : Peak finding algorithm

I also watched the youtube video from the MIT OCW channel.

As per my understanding, the algorithm is to find a LOCAL peak.

The top comment on the post says a peak is not necessarily a global maximum...but isn't global maximum a peak? Is this converse not true?

If I start by this algorithm then the INITIAL middle element decides which way the peak will be found. Any peak on the other side(LOCAL or GLOBAL) will be ignored.

Also in the lecture says, "IF IT EXISTS". What does that mean? How does it depend on the >= sign?

P.S: Point out wherever I am wrong.

Community
  • 1
  • 1
piepi
  • 141
  • 1
  • 4
  • 12

2 Answers2

3

The top comment on the post says a peak is not necessarily a global maximum...but isn't global maximum a peak? Is this converse not true?

A local maximum is not necessarily the global maximum, while the global maximum is one of the local maxima. I actually had this question in an interview once, any my interviewer helped me understand the concept by drawing a graph.

enter image description here

See here how the a local maximum is also the global maximum, but there are other local peaks which are not the global maximum.

If I start by this algorithm then the INITIAL middle element decides which way the peak will be found. Any peak on the other side(LOCAL or GLOBAL) will be ignored.

That is correct, this algorithm only finds a single local maximum. Any others are ignored.

If you want to find all of the local maxima and then decide which one is the global maximum, you must iterate through and look at every element, which then becomes a more trivial O(n) walk through of the array.

Nick Zuber
  • 5,467
  • 3
  • 24
  • 48
  • Since you got that in an interview I think you can share with us some of the practical applications for such algorithm. Would you ?. Thanks for the answer:) – MSaudi Jan 08 '19 at 08:08
0

The algorithm doesn't promise to find the maximum element, just a peak, which is an element that's greater than both its neighbors, so:

isn't global maximum a peak? Is this converse not true?

You're right, global maximum is a peak, but the converse is not always true.

INITIAL middle element decides which way the peak will be found

Again, you're right, but that's just what the algorithm does, it promises to find a peak, not the maximum. If you want the maximum, iterate over all peaks and find the greatest.

yelsayed
  • 5,236
  • 3
  • 27
  • 38