title: Searching for an element in log(n) time
body: <p>I came across the following question:</p>
  <blockquote>
  <p>Suppose I modify a given sorted list of 4n distinct numbers as follows:</p>
  <p>Keep elements in even positions (positions 2, 4, 6, ... 4n) 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.</p>
  <p>Now swap elements in positions i and j for every such pair. (i.e. every element in an odd numbered position in the ﬁrst 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 ﬁrst half of the array is swapped with some element in an odd numbered position in the second half. Now given an element x, explain how you can determine whether or not x is in the (new reshuﬄed) array in O(logn) time.</p>
  </blockquote>
  <p>Honestly, I am not sure about how to approach this one. Given x, I can search whether it exists at any even numbered position using binary search. But the numbers in the odd positions are no longer sorted.</p>
  <p>Any help is appreciated. Thanks!</p>