QUESTION$-9$

Suppose u modify a given sorted list of $4n$ distinct numbers as follows:

Keep elements in even positions $($positions $2,4,6,..\mathrm{.}4$n$)$ as they are. Form n disjoint pairs $($i$,$ j$)$

on the odd numbered positions where $i=2k+1$ for some $k=0$ to $n-1$ and $j=2k+1$ for some

$k=n$ to $2n-1.$ Now swap elements in positions i and $j$ for every such pair. $($I$.$e$.$ every element

in an odd numbered position in the first half of the array is swapped with some element in an

odd numbered position in the second half of the array. No element is involved in more than

one swap $($i$.$e$.$ the swaps are disjoint$).$ You don't know these $($i$,$ j$)$ pairs except that an element

in an odd numbered position in the first half of the array is swapped with some element in an

odd numbered position in the second half.

Now given an element $x,$ Design an algorithm that how you can determine whether or not $x$ is

in the $($new reshuffled$)$ array in $O(logn)$ time