# Decision tree complexity of finding parameters of “zigzag” array

I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:

An array is called a zigzag array if there are $$1 \leq i \leq j \leq n$$ so that the array increases from $$1$$ to $$i$$, decreases from $$i$$ to $$j$$, and increases from $$j$$ to $$n$$.

Input: a zigzag array. Output: the position of $$i$$ and $$j$$.

• Upper bound: just going on the array and finding $$i$$ and $$j$$, which takes $$O(N)$$.
• Lower bound: I think that we need to find pairs $$i$$ and $$j$$ for which $$k$$ is bigger than $$i$$ in $$n$$ elements, I don't know how to solve it.
The obvious lower bound is $\Omega(\log n)$, since there are $\binom{n+1}{2}$ possible answers. It is likely that using smart binary search you can find $i,j$ in $O(\log n)$ queries. I suggest starting with the easier case in which $j = n$, that is, the array increases and then decreases, and you want to find its maximum in $O(\log n)$ queries. Such arrays are known as bitonic, and indeed you can find $i$ in $O(\log n)$ comparisons (see for example this solution).