Optimal Search criteria in this array?

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, Qui开发者_Go百科ck 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. :(

---

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

---

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?

---

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

---

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)