二进制搜索在最坏情况下是否是最佳我的导师已经这么说了，但我找不到支持它的书 . 我们从有序数组开始，在最坏的情况下（对于该算法最坏的情况），任何算法总是比二进制搜索更多 pairwise comparisons .
很多人说这个问题不清楚 . 抱歉!所以输入是任何通用排序数组 . 我正在寻找一个证据，证明任何搜索算法在最坏的情况下至少会进行log2（N）比较（考虑到算法的最坏情况） .
最坏的情况是哪种算法？没有一个普遍的“最坏情况” . 如果你的问题是......
"Is there a case where binary search takes more comparisons than another algorithm?"
然后，是的，当然 . 如果元素恰好是列表中的第一个元素，则简单的线性搜索会花费更少的时间 .
"Is there even an algorithm with a better worst-case running time than binary search?"
是的，如果您对数据有更多了解 . 例如，基数树或特里结构在条目数方面是最差的恒定时间（但是密钥的长度是线性的） .
"Is there a general search algorithm with a better worst-case running time than binary search?"
如果你只能假设你在键上有一个比较函数，不，最好的最坏情况是O（log n） . 但是有些算法更快，只是没有大的意义 .
...所以我想你真的必须首先定义问题！
我认为这个问题有点不清楚，但仍然是我的想法 .
二进制搜索的最坏情况是在所有log n比较之后找到您要搜索的元素 . 但是相同的数据对于线性搜索来说是最好的情况 . 这取决于数据安排和您要搜索的内容，但二进制搜索的最坏情况最终将是log n . 现在，这不能与相同的数据进行比较并搜索线性搜索，因为它的最坏情况会有所不同 . 线性搜索的最坏情况可能是找到恰好位于数组末尾的元素 .
例如：数组A = 1,2,3,4,5,6和A上的二进制搜索为1将是最坏的情况 . 而对于相同的阵列，线性搜索6将是最坏的情况，而不是搜索1 .
二进制搜索具有最差的 O(log(N)) 比较的复杂情况 - 这对于基于比较的搜索排序数组是最佳的 .
O(log(N))
在某些情况下，除了纯粹基于比较的搜索之外，做一些其他事情可能是有意义的 - 在这种情况下，您可能能够击败 O(log(N)) 障碍 - 即检查interpolation搜索 .
是的，二进制搜索是最佳的 .
通过吸引信息理论可以很容易地看出这一点 . 仅需要 log N 位来识别 N 元素中的唯一元素 . 但每次比较只给你一点信息 . 因此，您必须执行 log N 比较以标识唯一元素 .
log N
N
更详细的...考虑一个在最坏的情况下优于二分搜索的假设算法X.对于数组的特定元素，运行算法并记录它要求的问题;即，它执行的比较序列 . 或者更确切地说，记录这些问题的答案（如"true, false, false, true"） .
将该序列转换为二进制字符串（1,0,0,1） . 将此二进制字符串称为“关于算法X的元素的签名” . 对数组的每个元素执行此操作，为每个元素分配“签名” .
现在这是关键 . 如果两个元素具有相同的签名，则算法X无法区分它们！所有算法都知道数组是从它提出的问题中得到的答案;即，它执行的比较 . 如果算法不能区分两个元素，那么它就不正确 . （换句话说，如果两个元素具有相同的签名，意味着它们会导致算法进行相同的比较序列，算法会返回哪个算法？矛盾 . ）
最后，证明如果每个签名的位数少于 log N ，则必须存在两个具有相同签名的元素（归类原则） . 完成 .
[更新]
一个快速的额外评论 . 以上假设该算法除了从执行比较中学到的内容外，对该数组一无所知 . 当然，在现实生活中，有时你会先验一些关于数组的知识 . 作为一个玩具示例，如果我知道数组有（比方说）10个元素都在1到100之间，并且它们是不同的，并且数字92到100都存在于数组中......那么显然我不知道即使在最坏的情况下也需要进行四次比较 .
更现实的是，如果我知道元素在它们的最小值和最大值之间均匀分布（或大致均匀分布），那么我可以做得比二分搜索更好 .
但在一般情况下，二分搜索仍然是最佳的 .
这取决于数据的性质 . 例如英语和字典 . 您可以编写一种算法，通过利用某些字母在英语语言中以不同频率出现的事实来实现比二分搜索更好的算法 .
但一般来说，二元搜索是一种安全的选择 .
5 回答
最坏的情况是哪种算法？没有一个普遍的“最坏情况” . 如果你的问题是......
"Is there a case where binary search takes more comparisons than another algorithm?"
然后，是的，当然 . 如果元素恰好是列表中的第一个元素，则简单的线性搜索会花费更少的时间 .
"Is there even an algorithm with a better worst-case running time than binary search?"
是的，如果您对数据有更多了解 . 例如，基数树或特里结构在条目数方面是最差的恒定时间（但是密钥的长度是线性的） .
"Is there a general search algorithm with a better worst-case running time than binary search?"
如果你只能假设你在键上有一个比较函数，不，最好的最坏情况是O（log n） . 但是有些算法更快，只是没有大的意义 .
...所以我想你真的必须首先定义问题！
我认为这个问题有点不清楚，但仍然是我的想法 .
二进制搜索的最坏情况是在所有log n比较之后找到您要搜索的元素 . 但是相同的数据对于线性搜索来说是最好的情况 . 这取决于数据安排和您要搜索的内容，但二进制搜索的最坏情况最终将是log n . 现在，这不能与相同的数据进行比较并搜索线性搜索，因为它的最坏情况会有所不同 . 线性搜索的最坏情况可能是找到恰好位于数组末尾的元素 .
例如：数组A = 1,2,3,4,5,6和A上的二进制搜索为1将是最坏的情况 . 而对于相同的阵列，线性搜索6将是最坏的情况，而不是搜索1 .
二进制搜索具有最差的
O(log(N))比较的复杂情况 - 这对于基于比较的搜索排序数组是最佳的 .在某些情况下，除了纯粹基于比较的搜索之外，做一些其他事情可能是有意义的 - 在这种情况下，您可能能够击败
O(log(N))障碍 - 即检查interpolation搜索 .是的，二进制搜索是最佳的 .
通过吸引信息理论可以很容易地看出这一点 . 仅需要
log N位来识别N元素中的唯一元素 . 但每次比较只给你一点信息 . 因此，您必须执行log N比较以标识唯一元素 .更详细的...考虑一个在最坏的情况下优于二分搜索的假设算法X.对于数组的特定元素，运行算法并记录它要求的问题;即，它执行的比较序列 . 或者更确切地说，记录这些问题的答案（如"true, false, false, true"） .
将该序列转换为二进制字符串（1,0,0,1） . 将此二进制字符串称为“关于算法X的元素的签名” . 对数组的每个元素执行此操作，为每个元素分配“签名” .
现在这是关键 . 如果两个元素具有相同的签名，则算法X无法区分它们！所有算法都知道数组是从它提出的问题中得到的答案;即，它执行的比较 . 如果算法不能区分两个元素，那么它就不正确 . （换句话说，如果两个元素具有相同的签名，意味着它们会导致算法进行相同的比较序列，算法会返回哪个算法？矛盾 . ）
最后，证明如果每个签名的位数少于
log N，则必须存在两个具有相同签名的元素（归类原则） . 完成 .[更新]
一个快速的额外评论 . 以上假设该算法除了从执行比较中学到的内容外，对该数组一无所知 . 当然，在现实生活中，有时你会先验一些关于数组的知识 . 作为一个玩具示例，如果我知道数组有（比方说）10个元素都在1到100之间，并且它们是不同的，并且数字92到100都存在于数组中......那么显然我不知道即使在最坏的情况下也需要进行四次比较 .
更现实的是，如果我知道元素在它们的最小值和最大值之间均匀分布（或大致均匀分布），那么我可以做得比二分搜索更好 .
但在一般情况下，二分搜索仍然是最佳的 .
这取决于数据的性质 . 例如英语和字典 . 您可以编写一种算法，通过利用某些字母在英语语言中以不同频率出现的事实来实现比二分搜索更好的算法 .
但一般来说，二元搜索是一种安全的选择 .