algorithm - 此数组中的最佳搜索条件？

Question

我刚刚写了这个试卷，其中有一个问题:考虑一个大小为 2n 的数组，其中奇数位置的数字按升序排列，偶数位置的数字按降序排列。现在，如果我必须在这个数组中搜索一个数字，这是执行此操作的好方法吗？选项是:

1. 快速排序然后二分查找
2. 合并两个排序好的数组，然后进行二分查找
3. 顺序搜索

在 1 中，快速排序需要 O(n log n) 和二进制搜索，O(log n)

2中，Merge取O(n)然后O(log n)进行二分查找

在 3 中，它需要 O(n)。

所以 3 原来是要走的路。那是对的吗？有没有更好的选择？

编辑:我接受了卢卡斯的回答，因为他是第一个。唉，那是另一种选择。我得到一个-1。 :(

Answer 1

您可以进行两次二进制搜索——即 O(log n)，因为您忽略了常量(在本例中为 2)。