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.

  • $\begingroup$ How many elements are swapped - is it a constant number? If not, I can choose O(n) elements to be swapped (say n/4 to be concrete), and then it cannot be O(log n) anymore... $\endgroup$ – TCSGrad May 11 '14 at 18:47


  1. Use binary search to find the possible locations of $x$ in the original array.

  2. If you find two even elements $y,z$ with $y<x<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.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.