在单调递增然后单调递减的序列中找到最大值或最小值可以在 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/