查找单调增加然后单调减少的序列中的最大值或最小值可以在 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
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
