c - 在单调递增然后递减的序列cera中找到一个数字

Question

在单调递增然后单调递减的序列中找到最大值或最小值可以在 O(log n) 中完成。

但是，如果我想检查一个数字是否存在于这样的序列中，是否也可以在 O(log n) 中完成？

我认为这是不可能的。考虑这个例子:1 4 5 6 7 10 8 3 2 0。

在这个例子中，如果我需要查找序列是否包含'2'，我没有任何条件将搜索空间划分为原始搜索空间的一半。在最坏的情况下，它将是 O(n)，因为当我们尝试搜索 2 时，您需要检查两半。

我想知道，这个搜索是否可以在 O(log n) 时间内完成？

Answer 1

如您所述，您可以在 O(logn) 中找到最大值(及其位置)。然后你可以在每个部分进行二进制搜索，这也是 O(logn)。

在上面的示例中，您在位置 5 找到最大值 10。然后在子序列 [0..5] (1, 4, 5, 6, 7, 10) 中进行二分查找。由于找不到 2，您继续在另一部分(10、8、3、2、0)中进行二分查找。

要在 O(logn) 中找到最大值:查看中心的两个元素:7 < 10。因此我们仍处于递增部分，必须在序列的右半部分寻找最大值:( 10、8、3、2、0)。查看 8 和 3，然后继续左边的部分 (10, 8)。