Optimal Search criteria in this array?

Question

I just wrote this exam, in which there was question: Consider a array of size 2n, where the numbers in odd positions are sorted in ascending order and the the numbers in even positions in descending order. Now, if I have to search for a number in this array, which is a good way to do this? The options were:

1. Quick sort and then binary search
2. Merge the two sorted arrays and then binary search
3. Sequential search

In 1, Quick Sort takes O(n log n) and binary search, O(log n)

In 2, Merge takes O(n) and then O(log n) for binary search

In 3, it takes O(n).

So 3 turns out to be the way to go. Is that correct? Is there a better choice which might not have been given?

EDIT: I accepted Lukas's answer since he was the first. Sigh, that was the other option. I get a -1. :(

Answer 1

You can do two binary searches -- that's O(log n), because you ignore constants (2 in this case).

Answer 2

Would it not be easier if you just did a binary search on both sets? Thus O(log n) and O(log n)?

Would that not be easier, so if found in the first, the second step is not even required?

Answer 3

Check whether it's even or odd, and binary search on the part of the array you're interested in. O(log n).

Answer 4

I think second option fits your criteria.

Merge sort: We can easily get full array of sorted numbers from two half sorted arrays with time complexity of O(n)

And then binary search will have time complexity of O(logn)