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.

$($b$)$ Write a recurrence for the running time of the algorithm