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.