 # DE Shaw Interview Question| Search in Shuffled sorted array

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
``````