Consider a list $\boldsymbol{x}=x_0,x_1,\ldots,x_{n-1}$, which we consider to be circular by taking the subscripts modulo $n$. The entries in the list are distinct integers.

A *local pattern* is a Boolean expression $P(i)$ involving inequalities between the values $x_i,x_{i+1},\ldots,x_{i+k}$ for some constant $k$. For example, we might have $P(i)=(x_i\lt x_{i+1})\wedge(x_i\lt x_{i+2})$. "Finding $P~$ in $\boldsymbol{x}$" means
finding a value of $i$ for which $P(i)$ is true, or determining that there is no such $i$.

Trivially, we can find any local pattern in $\boldsymbol{x}$ in $O(n)$ time just by trying each $i$. Perhaps surprisingly, some nontrivial local patterns can be found in $O(\log n)$ time. Consider the pattern for a local minimum $P(i)=(x_i\gt x_{i+1})\wedge(x_{i+1}\lt x_{i+2})$. Choose any three distinct entries $x_i,x_j,x_k$, where $x_j$ is the least. Without loss of generality, we can assume that $0\le i\lt j\lt k\lt n$. Let $\ell~$ be the midpoint (rounded towards $j$) of the longest of the intervals $[i,j]$ and $[j,k]$. If $x_j\lt x_\ell$, $x_j$ is the least of $x_i,x_j,x_\ell$, while if $x_j\gt x_\ell$, $x_\ell$ is the least of $x_j,x_\ell,x_k$. It is easy to see that continuing in this fashion finds a local minimum in $O(\log n)$ steps.

**The question is:** which local patterns can be found in $O(\log n)$ steps?