Fix an array A$[1$ : n$]$ with distinct entries. This array may not be sorted. An index $2<=$ j $<=$ n $1$ is a

local minimum if A$[$ j $1]>$ A$[$ j $]$ and A$[$ j $+1]>$ A$[$ j $].1$ is a local minimum if A$[1]<$ A$[2]$ and n is a

local minimum if A$[$n$]<$ A$[$n $1].$

Design an O$($log n$)$ algorithm to find some local minimum.

You need to give an argument of why your algorithm is correct. $($A $$formal proof$$ via induction

defining predicates etc is not needed; what is needed is the key observation that convinces a reader

why your algorithm is correct.$)$