Recently I have encountered a problem regarding searching.Any help would be appreciated.It says let, *A* be a sorted array(1-based index) of size *n* where *n* is even.A new array *B* is generated by swapping some elements in odd-numbered positions in the first half of *A* with some elements in odd-numbered positions in the second half of *A*.Note that elements in the even numbered positions are the same in both *A* and *B*, whereas each element in an odd-numbered position in *A* takes part in at most one swap.Write an algorithm that takes *A* and an integer *x* as inputs and finds whether *x* is present in *B* or not.

You can store the array in a map and then try to search the element because in map, time complexity of searching element by using the find function is O(logn). I hope it helps..

I forgot to mention that only primitive data types can be used.

B is basically reordered A (each element in an odd-numbered position in A takes part in at most one swap). Just do binary search on A. If X in A — it's in B.