Problem $2$: Peak Finding Problem $[$Advanced$]$

Let us come up with an $$improved$$ algorithm for Peak Finding. First, let us study the problem $$ is it possible for an array to not have a peak?

The answer is no$.$ Any array will have at least one peak. We can prove this by contradiction.

Proof that an array of numbers will have at least $1$ peak.

Assume the statement is not true; in other words, there is an array with no peak. Consider this array $[$of n elements$]$; let us call it as X$[1..$n$]$

As X$[1]$ is not a peak, we know that X$[1]<$ X$[2].$

Now, because X$[2]$ is not a peak, and because X$[2]>=$ X$[1],$ we know that X$[2]<$ X$[3]$

Similarly, go on and we know that X$[3]<$ X$[4],$ X$[4]<$ X$[5]$ and so on$,$ and X$[$n $1]<$ X$[$n$].$

However, if that is the case, then X$[$n$]$ is a peak because X$[$n$]>=$ X$[$n $1].$

Therefore we have proved that an array of n elements MUST have at least $1$ peak.

$($a$)$ Answer the following: Come up with an array of $5$ elements with $2$ peaks.

$[5,2,3,4,1]$

Below, we give an improved algorithm for peak finding.

Input: Array A$[1..$n$],$ indexes x and y$,$ and we are finding a peak in A$[$x$..$y$]$

Return: index i $($x $<=$ i $<=$ y$),$ such that A$[$i$]$ is a peak

PeakFindingImproved$($A$,$ x$,$ y$)$:

$1.$ mid $=($x $+$ y$)/2$

$2.$ if A$[$mid$]<$ A$[$mid $1]$

$3.$ return PeakFindingImproved$($A$,$ x$,$ mid $1)$

$4.$ else if A$[$mid$]<$ A$[$mid $+1]$

$5.$ return PeakFindingImproved$($A$,$ mid $+1,$ y$)$

$6.$ return mid

Proof of Correctness of PeakFindingImproved algorithm

Consider Step $3.$ This will be executed only if A$[$mid $1]>$ A$[$mid$]$ Therefore, any element that is a peak in A$[$x$..$mid $1]$ will be a peak. For indexes $<($mid $1),$ it is obvious; if $($mid $1)$ is a peak in A$[$x$..$mid $1],$ then we know $($mid $1)$ is a peak in A$[$x$..$y$],$ because A$[$mid $1]>=$ A$[$mid $2]($from Step $3$ in Algorithm$)$ and A$[$mid $1]>=$ A$[$mid$]($from Step $2$ in Algorithm$).$ We can similarly prove for Step $5.$ We can also prove Step $6$ is correct, when Step $6$ is executed.