在单调递增然后单调递减的序列中找到最大值或最小值可以在 O(log n) 中完成。
但是,如果我想检查一个数字是否存在于这样的序列中,是否也可以在 O(log n) 中完成?
我认为这是不可能的。考虑这个例子:1 4 5 6 7 10 8 3 2 0。
在这个例子中,如果我需要查找序列是否包含'2',我没有任何条件将搜索空间划分为原始搜索空间的一半。在最坏的情况下,它将是 O(n),因为当我们尝试搜索 2 时,您需要检查两半。
我想知道,这个搜索是否可以在 O(log n) 时间内完成?
最佳答案
如您所述,您可以在 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)。
关于c - 在单调递增然后递减的序列cera中找到一个数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11536123/