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
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