Search for an item in log (n) time

Question

I came across the following question:

Suppose I modify this sorted list of 4n different numbers as follows:

Keep the elements in even positions (positions 2, 4, 6, ... 4n) as they are. Make up n disjoint pairs (i, j) at 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 replace the elements at positions i and j for each such pair. (i.e. each element in an odd numbered position in the first half of the array is replaced by 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 do not intersect) You do not you know these (i, j) pairs, except that an element in an odd numbered position in the first half of the array exchanges some element in an odd numbered position in the second half. Now, taking into account the element x, explain how you can determine if whether x in (new res hu ffl ed) in O (logn) time.

Honestly, I'm not sure how to approach this. Given x, I can do a search to see if it exists in any even position using binary search. But numbers in odd positions are no longer sorted.

Any help is appreciated. Thank you

Answer 1

You can determine if any element x in a new (shuffled) set by doing two binary searches. The key here is that the odd elements essentially act as “keys” to each other, as they have been replaced by disjoint pairs.

• Use the standard binary search to search for x , making sure you always select even indexes for comparison. (Using even indices is crucial because these are elements that are still in order.)

• If x is in an even indexed array, 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 that if the array was still sorted, x must be an element between m and n (if it was in the array).

• Consider an element in the index between m and n - call this y . If the element x was in the original array, it should have been replaced with y when creating the shuffled array.

• Perform a second binary search to search for y , again ensuring that you will only select indexes for comparison. Similar 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, the y element will be the element between m' and n' .

• The element between m' and n' must be any element that has been replaced by y , and therefore any element was originally between m and n . If this value is not x , then x does not exist in the array.