DE Shaw Interview Question| Search in Shuffled sorted array

1

Initially there is a sorted array. Say, Initially array A was

A=  0   0   1   2   5   6   8   8   9  10 
i=  0   1   2   3   4   5   6   7   8   9

Following 3 operations are performed to obtain B from A

  1. Copy elements in even indices from A to B
  2. Split odd indices into two parts left and right . If there are odd number of odd indices ignore middle most odd number when computing left and right so that both have same number of odd numbers.
  3. For every odd index in left , swap it with some odd index in right .
    For example, B can be
B= 0  10   1   8   5   |6|   8   2   9   0 
i= 0   1   2   3   4   |5|   6   7   8   9

(|| used to show left and right)
B could also be

B= 0   8   1  10   5   |6|   8   0   9   2 
i= 0   1   2   3   4   |5|   6   7   8   9

Search in this array B for key k.

Another simpler example,

  A= 0   1   2   3   4   |5|   6   7   8   9 
  i= 0   1   2   3   4   |5|   6   7   8   9

B can be

  B= 0   7   2   9   4   |5|   6   1   8   3 
  i= 0   1   2   3   4   |5|   6   7   8   9

or

A= 0   9   2   7   4   |5|   6   3   8   1 
i= 0   1   2   3   4   |5|   6   7   8   9