二分查找的最优性
这可能是一个愚蠢的问题，但是有人知道二分搜索是渐近最优的证明吗？也就是说，如果给我们一个排序的元素列表，其中对这些对象唯一允许的操作是比较，那么如何证明搜索不能在 o(lg n) 中完成？ （顺便说一句，这是 lg n 的小-o。）请注意，我将其限制为唯一允许的操作是比较的元素，因为有一些众所周知的算法可以在预期上击败 O(lg n)如果允许您对数据执行更复杂的操作（例如，参见插值搜索）。
This may be a silly question, but does anyone know of a proof that binary search is asymptotically optimal? That is, if we are given a sorted list of elements where the only permitted operation on those objects is a comparison, how do you prove that the search can't be done in o(lg n)? (That's little-o of lg n, by the way.) Note that I'm restricting this to elements where the only operation permitted operation is a comparison, since there are well-known algorithms that can beat O(lg n) on expectation if you're allowed to do more complex operations on the data (see, for example, interpolation search).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
来自此处：
From here:
逻辑很简单。假设我们有 n 个不同排序元素的数组。
n <= 2。否则，如果我们有 3 个元素 (a, b, c)，并且我们的算法有 2 个可能的结果，则永远不会选择 3 个元素之一。n <= 4。k比较足够，n应该是n <= 2^k。将最后一个不等式反转即可得到对数：
k >= log(2, n)。The logic is simple. Let's assume we have array of
ndifferent sorted elements.n <= 2. Otherwise, if we have 3 elements (a, b, c) and our algorithm has 2 possible outcomes, one of 3 elements will never be selected.n <= 4.kcomparisons to be enoughnshould ben <= 2^k.Reverse the last inequality and you'll have logarithm:
k >= log(2, n).正如 Nikita 所描述的，不可能有比 O(log n) 更好的东西总是。
即使您允许执行一些额外的操作，但这仍然不够 - 我确信可以准备元素序列，其中插值搜索的性能比二分搜索更差。
我们可以说插值搜索更好，只是因为：
所以答案是——这完全取决于我们对传入数据集的额外了解。
As Nikita described it's impossible to have something always better than O(log n).
Even if you allowed to do some additional operations, it's still not enough - I'm sure it's possible to prepare elements sequence where interpolation search will perform worse than binary search.
We can say interpolation search is better only because:
So the answer is - it all depends on the additional knowledge we have about incoming data sets.