$******$ Given an array $A[0..n-1]$ where we imagine $A[-1]=A[n]=-$ we want to find a peak.

$A[i]$ is a peak if is not smaller than its neighbor$($s$)$:

$A[i-1]A[i]A[i+1]$

For example, in the following array elements $6$ and $7$ are peaks.

$A$:$-\{\begin{array}{ccc}\text{:}[1,& 2,6,5,3,7,& 4]\end{array}******$ Given an array $A[0..n-1]$ where we imagine $A[-1]=A[n]=-$ we want to find a peak.

$A[i]$ is a peak if it is not smaller than its neighbor$($s$)$:

$A[i-1]A[i]A[i+1]$

For example, in the following array elements $6$ and $7$ are peaks.

$A$:$-\{\begin{array}{ccc}\text{:}[1,& 2,6,5,3,7,4,& -]\end{array}$

Give an algorithm that finds any peak in $O(logn)$ time. Your algorithm should include the

analysis of the run time and a full proof of correctness.