二分搜索的最优性

Question

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

Answer 1

从这里：

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