The Peak Finder algorithm finds a peak element in an array. A peak element is defined as an

element that is greater than or equal to its neighbors. In the case of an array with multiple

peaks, the algorithm returns any one of them. You can assume that an element is always

considered to be strictly greater than a neighbor that is outside the array. In other words, in

case of the edges, you only need to look at only one side.

The Peak Finder algorithm works as follows:

Input: A $($array of integers$),$ left $($start index$),$ right $($end index$)$

Output: Index of a peak element

Algorithm PeakFinder$($A$,$ left, right$)$

mid $=($left $+$ right$)//2$

if $($mid $==$ left or A$[$mid$]>=$ A$[$mid $-1])$ and $($mid $==$ right or A$[$mid$]>=$ A$[$mid $+1])$ then

return mid

else if mid $>$ left and A$[$mid $-1]>$ A$[$mid$]$ then

return PeakFinder$($A$,$ left, mid $-1)$

else

return PeakFinder$($A$,$ mid $+1,$ right$)$

Prove that the Peak Finder algorithm correctly identifies a peak element.