Minimal element in logarithmic time

Suppose $$A$$ is an array of distinct natural numbers. We call an element $$A[i]$$ minimal if it's less than both the element before and after it (if any). Present a worst-case $$O(\log n)$$ algorithm for finding a minimal element. I wanted to find the minimum (since it's less than all the elements) and then use binary search with it as a key but you can't find minimum in logarithmic time. My other idea was to categorize the elements into three-element groups but it doesn't work as well. We should probably solve this question with divide and conquer approach.

• When $$A[i]\le A[i-1]$$, go "forward" in the search (increment the left pointer)
• When $$A[i] > A[i-1]$$, go "backward" in the search (decrement the right pointer)
• the "increment" or "decrement" operations means to take either the right or the left pointers (lets call the pointer we do the operation on $p$) and do $p \leftarrow i$, just as you would in a normal binary search. Its easy to understand why this is logarithmic (it is for the same reason that binary search is), but it is more tricky to understand why this procedure returns a correct answer. Try to prove it for yourself :) Aug 21 '21 at 16:33
Note that, in your idea, because of you search for minimum element, the running time will be $$\Omega(n)$$, but you can solve your problem in $$\mathcal{O}(\log n)$$.