Peak finding problem

Given an array you have to find a peak if it exists.
A peak is an array element which is greater than equal to is adjacent element.
For example in [1,2,4,3] , 4 is a peak.
In [5,6,7,8] 8 is a peak.
My doubt is will there be always a peak in an array.
If so,how can we prove it?

Link to the problem?

Actually,I saw it on data structure course of mit ocw.

1 Like

Link to the video: https://www.youtube.com/watch?v=HtSuA80QTyo

1 Like

A simple solution would be as follows.
Claim : The greatest element in the array is a peak of the array.

Proof

Let the greatest element in the array (this will always exist) be A_x, where A_i represents the i^{th} element in the array.
Assume A_x is not the peak. Then A_x < A_{x-1} and A_x < A_{x+1}. But this implies that A_x is not the greatest element in the array.
Thus contradiction and we are done.

5 Likes

Got it.Thank you so much.

1 Like