How to check if $\text{position}\left(\frac{a + b} 2\right )$ is in range $\text{position}\left(a\right )$ and $\text{position}\left(b\right )$

Question

Given a permutation of $n$ number $1, 2, 3,\dots,n$. How to check if it is exist $a,\ b$ with the same parity such that $\frac {a + b} 2$ is between $a, b$.

How to solve this problem efficiently ? (approximate algorithm is good too)

Answer 1

My first idea: Let's say you have numbers $x,y,z$ in your permutation with $y=\frac{x+z}{2}$ and they appear in that order. This means $y-x=z-y$ must hold true. Now iterate through all possible values of $y$, i. e. all numbers at position $2,\dots,n-1$ and generate two lists: calculate $y-x$ for all values $x$ left of $y$, and $z-y$ for all values $z$ to the right of $y$. If you find a matching number in these lists, answer is yes, otherwise no.

Example: Permutation is $(5,1,6,4,2,7,3)$. First step $y=1$ yields the lists: $(-4)$ and $(5,3,1,6,2)$ with no matches. In the second step $y=6$ we get $(\mathbf{1},5)$ and $(-2,-4,\mathbf{1},-3)$. The matching number 1 corresponds to 5, 6 and 7 in the permutation. This should have cubic time complexity. If that's not fast enough for you, I would consider using some sort of tree based algorithm.

Update: I implemented this algorithm and made some tests. For a random permutation the algorithm is quite fast and can compute the answer up to $n=100000$ in a matter of seconds. But of course, the bigger your $n$, the harder it gets to find a permutation which doesn't have the desired property: For example for $n=9$ we already have 99.9 % permutations which stand the test. So most of the times you only have to compute some of the lists in order to get the result. But if you had to check all of the permutations for a given n you're gonna need some other methods...