Sorted array with odd indexed elements swapped randomly
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.