Sorted array with odd indexed elements swapped randomly A sorted array $\mathcal{A}$ with even number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}_1, \mathcal{A}_2$) contain equal number of elements. We choose some arbitary odd indexed (index with $1,5,9$ etc.) elements from $\mathcal{A}_1$ and swap them with some other random odd indexed elements of $\mathcal{A}_2$. Even indexed elements of $\mathcal{A}$ remain untouched.


We need to device an algorithm to check whether an element $\mathcal{x}$ exists in $\mathcal{A}$ in $O(\log n)$ time.
Hint:


Use binary search to find the possible locations of $x$ in the original array.
If you find two even elements $y,z$ with $y&lt;x&lt;z$ and the element between them $w$ is does not belong there, then $w$ might have been switched with $x$. Find the proper position of $w$ using binary search and look if $x$ is there.