Peak finding algorithm
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!
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.
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.