在最坏的情况下二分搜索是否是最优的？我的老师是这么说的，但我找不到支持它的书。我们从一个有序数组开始，在最坏的情况下（该算法的最坏情况），任何算法总是会花费更多成对比较比二分查找。
很多人表示这个问题不清楚。对不起！所以输入是任何通用的排序数组。我正在寻找一个证明，表明任何搜索算法在最坏情况下都将至少进行 log2(N) 比较（考虑的算法的最坏情况）。
是的，二分搜索是最佳的。
通过诉诸信息论，这一点很容易看出。它需要log N位只是为了identify一个独特的元素N元素。但每次比较只能提供一点信息。因此，您必须执行log N比较以确定独特的元素。
更详细地说...考虑一个假设的算法 X，它在最坏的情况下优于二分搜索。对于数组的特定元素，运行算法并record它提出的问题；即它执行的比较的顺序。或者更确切地说，记录answers这些问题（例如“真，假，假，真”）。
将该序列转换为二进制字符串 (1,0,0,1)。将此二进制字符串称为“元素相对于算法 X 的签名”。对数组的每个元素执行此操作，为每个元素分配一个“签名”。
现在关键就在这里。如果两个元素具有相同的签名，那么算法 X 无法区分它们！算法对数组的所有了解都是它从提出的问题中得到的答案；即它执行的比较。如果算法无法区分两个元素，那么它就不可能是正确的。 （换句话说，如果两个元素具有相同的签名，这意味着它们会导致算法进行相同的比较序列，那么算法会返回哪一个？矛盾。）
最后证明如果每个签名的数量少于log N位，则必须存在两个具有相同签名的元素（鸽子洞原理）。完毕。
[update]
一个简短的补充评论。上面假设算法除了从执行比较中学到的知识之外，对数组一无所知。当然，在现实生活中，有时你确实对数组有所了解a priori。作为一个玩具示例，如果我知道数组有（比如说）10 个元素，全部在 1 到 100 之间，并且它们是不同的，并且数字 92 到 100 都存在于数组中......那么显然我不知道即使在最坏的情况下也需要进行四次比较。
更现实的是，如果我知道元素在最小值和最大值之间均匀分布（或大致均匀分布），那么我可以做得比二分搜索更好。
但一般情况下，二分查找仍然是最优的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
