在最坏的情况下二进制搜索优化？ [英] Is binary search optimal in worst case?

问题描述

是在最坏的情况下二进制搜索优化？我的导师曾这样说过，但我找不到一本书备份它。我们先从一个有序阵列，而在最坏的情况下（最坏情况的算法），所有的算法总是会采取更多的两两比较比二进制搜索。

Is binary search optimal in worst case? My instructor has said so, but I could not find a book that backs it up. We start with an ordered array, and in worst case(worst case for that algorithm), any algorithm will always take more pairwise comparisons than binary search.

很多人说，这个问题还不清楚。抱歉!所以输入是任何一般排序阵列。我要寻找一个证明它说，任何搜索算法至少需要LOG2（N），在最坏的情况下比较（最坏情况考虑到算法中）。

Many people said that the question was unclear. Sorry! So the input is any general sorted array. I am looking for a proof which says that any search algorithm will take at least log2(N) comparisons in worst case(worst case for the algo in consideration).

推荐答案

是的，二进制搜索是最优的。

Yes, binary search is optimal.

这是很容易看到诉诸于信息理论。它采用日志N 位仅仅的确定的一个独特的元素出 N 元素。但每次比较只给你一个比特的信息。因此，您必须执行日志N 进行比较，以确定一个独特的元素。

This is easily seen by appealing to information theory. It takes log N bits merely to identify a unique element out of N elements. But each comparison only gives you one bit of information. Therefore, you must perform log N comparisons to identify a unique element.

更多冗长...考虑一个假想的算法X中优于在最坏情况下的二进制搜索。对于数组的特定元素，运行算法的记录的它提出的问题;即，比较的序列它执行。或者说，记录的的答案的这些问题（如真的，假的，假的，真正的）。

More verbosely... Consider a hypothetical algorithm X that outperforms binary search in the worst case. For a particular element of the array, run the algorithm and record the questions it asks; i.e., the sequence of comparisons it performs. Or rather, record the answers to those questions (like "true, false, false, true").

将其转换序列为二进制字符串（1,0,0,1）。称这种二进制串的元素相对于算法X签字。做到这一点的阵列的每个元素，分配一个签名的每个元素

Convert that sequence into a binary string (1,0,0,1). Call this binary string the "signature of the element with respect to algorithm X". Do this for each element of the array, assigning a "signature" to each element.

现在这里是关键。如果两个元素具有相同的签名，那么算法X不能告诉他们分开！所有的算法知道数组是从它提出的问题得到解答;即，它执行的比较。并且如果该算法不能告诉两个元件分开，那么它可以是不正确的。 （换句话说，如果两个元素具有相同的签名，也就是说，它们导致比较由该算法，其中之一做了算法返回？矛盾相同的序列。）

Now here is the key. If two elements have the same signature, then algorithm X cannot tell them apart! All the algorithm knows about the array are the answers it gets from the questions it asks; i.e., the comparisons it performs. And if the algorithm cannot tell two elements apart, then it cannot be correct. (Put another way, if two elements have the same signature, meaning they result in the same sequence of comparisons by the algorithm, which one did the algorithm return? Contradiction.)

最后，证明了如果每个签名具有比较少的日志N 位，则一定存在两个元素具有相同签名（鸽笼原理）。完成。

Finally, prove that if every signature has fewer than log N bits, then there must exist two elements with the same signature (pigeonhole principle). Done.

[更新]

一个快速的附加注释。上述假设，该算法并不知道，除了它的执行比较得知阵列任何事情。当然，在现实生活中，有时你知道一些关于数组的的先验的。作为玩具例如，如果我知道数组有（比方说）10个元素都为1至100，而且它们是不同，并且该号码92至100都是present阵列中...则显然我并不需要，即使在最坏的情况下执行四个比较

One quick additional comment. The above assumes that the algorithm does not know anything about the array except what it learns from performing comparisons. Of course, in real life, sometimes you do know something about the array a priori. As a toy example, if I know that the array has (say) 10 elements all between 1 and 100, and that they are distinct, and that the numbers 92 through 100 are all present in the array... Then clearly I do not need to perform four comparisons even in the worst case.

更现实的是，如果我知道元素的最小和最大他们之间均匀分配（或大致均匀分布），我又可以做的比二进制搜索更好。

More realistically, if I know that the elements are uniformly distributed (or roughly uniformly distributed) between their min and their max, again I can do better than binary search.

但是，在一般的情况下，二分搜索仍然是最佳

But in the general case, binary search is still optimal.

这篇关于在最坏的情况下二进制搜索优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！