二进制搜索的最佳性

Question

这可能是一个愚蠢的问题，但是有人知道二进制搜索在渐近上是最佳的证据吗？也就是说，如果我们获得了一个分类的元素列表，在这些元素中，这些对象上唯一允许的操作是一个比较，那么您如何证明无法在O（lg n）中进行搜索？ （顺便说一句，这是LG N的小o。）请注意，我将其限制在唯一允许操作的元素中，因为有一些众所周知的算法可以击败O（lg n）。如果允许您对数据进行更复杂的操作（例如，请参见插值搜索）。

Answer 1

从 这里:

• 可能的结果的数量至少应为O（n）。
• 您可以用“决策树”的节点来表示算法所做的决策：如果项目比较更大，那么它会继续前进，如果没有，则它会发生相反的方式。树的节点是算法的状态，叶子是结果。因此，树上至少应该有O（n）节点。
• O（n）节点上的每个树都至少具有O（log n）级别。

Answer 2

逻辑很简单。假设我们有 n 不同的分类元素。

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

扭转最后的不平等现象，您将具有对数： k >= log(2, n).

Answer 3

正如尼基塔（Nikita）所描述的那样，不可能有东西 总是 比O（log n）更好。

即使您允许进行一些其他操作，它仍然不够 - 我相信可以准备插值搜索的元素序列，而插值搜索的性能会比二进制搜索更糟。

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

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

因此，答案是 - 这完全取决于我们对传入数据集的其他知识。