ISI 2014 C2

Question

S[1 . . . n] is a sorted array of n integers, where n is even. A new
array S′ is generated by swapping some elements in odd-numbered
positions in the first half of S with some elements in odd-numbered
positions in the second half of S. Note that the elements in the even numbered positions are the same in both S and S′, whereas each element in an odd-numbered position in S takes part in at most one swap.
Write an O(log n) algorithm that takes S′ and an integer x as inputs
and finds whether x is present in S′ or not