Searching for an element in log(n) time

Question

I came across the following question:

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

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.

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, explain how you can determine whether or not x is in the (new reshuffled) array in O(logn) time.

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.

Any help is appreciated. Thanks!

Answer 1

You can determine whether some element x is in the new (shuffled) set by doing two binary searches. The key here is that the odd elements essentially act as "keys" for each other, since they have been swapped in disjoint pairs.

1. Use a standard binary search to look for x, making sure that you always choose even indices for comparison. (Using the even indices is crucial, because those are the elements that are still in order.)

2. If x is in the array at an even index, it will be found. If not, we will eventually find two elements m and n such that m < x < n and index(n) - index(m) == 2. This means if the array was still sorted, x would have to be the element between m and n (if it was in the array).

3. Consider the element at the index between m and n - call this y. If element x was in the original array, it must have been swapped with y when creating the shuffled array.

4. Perform a second binary search to look for y, again ensuring you only choose even indices for comparison. Similarly to step 2, you will eventually find two elements m' and n' such that m' < y < n' and index(n') - index(m') == 2. If the array was still sorted, element y would be the element between m' and n'.

5. The element between m' and n' must be whichever element was swapped with y, and therefore whatever element was originally between m and n. If this value is not x, then x does not exist in the array.