algorithm - 二分搜索的最优性

Question

这可能是一个愚蠢的问题，但有人知道二分搜索是渐近最优的证明吗？也就是说，如果给定一个元素的排序列表，其中对这些对象的唯一允许操作是比较，你如何证明搜索不能在 o(lg n) 中完成？（顺便说一下，这是 lg n 的小 O。）请注意，我将其限制为唯一允许操作是比较的元素，因为有众所周知的算法可以在预期上击败 O(lg n)如果允许您对数据执行更复杂的操作（例如，请参见插值搜索）。

Answer 1

从这里：

• 可能结果的数量应至少为 O(n)。
• 您可以通过“决策树”的节点来表示算法所做的决策：如果项目比较大，则继续进行，否则则继续。树的节点是算法的状态，叶子是结果。所以树中应该至少有 O(n) 个节点。
• O(n) 个节点上的每棵树至少有 O(log N) 个级别。

Answer 2

正如 Nikita 所描述的，不可能总是有比 O(log n) 更好的东西。

即使您允许执行一些额外的操作，这仍然不够 - 我确信可以准备元素序列，其中插值搜索的性能会比二分搜索更差。

我们可以说插值搜索更好，只是因为：

1. 我们考虑平均性能，而不是最坏的情况。
2. 每个可能的传入数据集的概率是不均匀的。

所以答案是——这一切都取决于我们对传入数据集的额外了解。

Answer 3

逻辑很简单。假设我们有n不同排序元素的数组。

1. 1 次比较有 2 种可能的结果（第一个元素更小或更大）。因此，如果一个比较就足够了，n <= 2. 否则，如果我们有 3 个元素 ( a, b, c) 并且我们的算法有 2 个可能的结果，则永远不会选择 3 个元素之一。
2. 2 次比较有 4 种可能的结果。因此，如果 2 次比较就足够了，n <= 4.
3. 同样，要k进行足够的比较，n应该是n <= 2^k.

反转最后一个不等式，您将得到对数：k >= log(2, n)。