此阵列中的最佳搜索条件？

Question

我只写了这个考试,其中有一个问题:考虑大小2n,其中在奇数位置的编号升序和降序排列偶数位置的数字进行排序的数组.现在,如果我必须在这个数组中搜索一个数字,这是一个很好的方法吗？选项是:

1. 快速排序然后二元搜索
2. 合并两个排序的数组,然后二进制搜索
3. 顺序搜索

1,快速排序采用O(n log n)和二分搜索,O(log n)

在2中,Merge采用O(n)然后采用O(log n)进行二进制搜索

在3中,它需要O(n).

所以3结果是要走的路.那是对的吗？有没有更好的选择可能没有给出？

编辑:我是第一个接受Lukas的回答.叹了口气,这是另一种选择.我得到-1.:(

Answer 1

您可以执行两次二进制搜索 - 即O(log n),因为您忽略常量(在本例中为2).