1
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by D.W., Juho, Wandering Logic, David Richerby, Luke Mathieson May 12 '14 at 23:21

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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
2
$\begingroup$

Hint:

  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.

$\endgroup$

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