algorithm - 二分查找

Question

所以，我想更多地了解二进制搜索，因为我不太明白。二进制搜索需要一个先决条件，即数组已排序。我说对了吗？似乎一个方法应该检查这个前提条件，如果不满足就抛出异常。但是，为什么检查前提条件是个坏主意？

score 8 · Accepted Answer

这是一个坏主意，因为检查数据是否已排序需要一些n步骤。整个搜索是关于log(n)步骤的。
如果你要检查，你不妨做一个线性搜索。

score 7 · Accepted Answer

二分搜索的重点在于，由于数据已经排序，您可以快速找到所需的信息。

拿按姓氏排序的电话簿。

如何在电话簿中找到某人？您将其打开到您认为将接近您想要的页面的页面，然后开始翻页。

但是你不是每次都翻一页，如果你错过了很多，你会翻一堆页，然后最后开始一次翻一页，直到最后你开始看一页。

这就是二分查找的作用。由于数据已排序，它知道它可以跳过很多内容并重新查看，它会专注于您想要的信息。

二进制搜索对每双倍数量的项目进行 1 次比较。因此，一个 1024 个元素的集合最多需要进行大约 10 次比较才能找到您的信息，或者至少找出它不存在。

如果您在运行实际的二分搜索之前，进行了完整的运行以检查数据是否已排序，那么您最好只扫描信息。完整的遍历 + 二分搜索将需要 N + log2 N 次操作，因此对于 1024 个元素，大约需要 1034 次比较，而对信息的简单扫描平均需要一半，即 512。

所以如果你不能保证数据是有序的，你就不应该使用二分查找，因为它会被简单的扫描胜过。

编辑：不过我会这么说，您可以添加一个仅调试代码步骤来验证这一点，以捕获应该为二进制搜索准备数据的代码中的错误，但是由于我上面写的内容，请知道这一点，这将使总运行时间增加很多，因此根据您要对此检查执行的操作，您可能想要也可能不想添加它。但它不应该出现在发布代码中。

score 3 · Accepted Answer

是的，二分查找涉及 0(log n) 个步骤，验证整个序列是否已排序涉及 0(n) 个步骤。从我的角度来看，最好在 DEBUG 模式下验证它，而不是在 RELEASE 期间。

score 1 · Accepted Answer

二分搜索假定输入数据已排序。所以在这里你是对的。

现在通常检查数据是否已排序一段时间。因此，在每次搜索之前执行此操作会使搜索效率低下。

更多细节。

假设“n”是您的数据量。

二分查找需要O(log(n))在最坏的情况下进行操作才能找到一个元素。确保数据排序需要O(n)操作。

因此，如果我们每次都检查非常大的前提条件，n我们将开始将大部分时间花在检查前提条件上，而不是进行实际搜索。

并且不难说你什么时候会看到这样的效果。我刚刚计算了您将花费多少时间进行预检查与实际搜索

等等。在每种情况下，按时休息都花在前提条件检查上。

score 0 · Accepted Answer

除了其他人所说的关于运行时间的内容（O(n) 检查所有项目，O(log(n)) 运行二进制搜索。）

我认为您误解了先决条件的概念。前置条件和后置条件是一个合同。如果您的先决条件为真，并且您运行算法，那么您的后置条件将为真。如果您的先决条件为假，那么您对后置条件不做任何保证。

所以基本上，二进制搜索是这样说的：如果你给我的数据已经排序，那么我可以告诉你特定数据的位置，或者如果它不存在，通过执行大约 log(n) 检查。如果数据未排序，我不保证我的答案。

如果你的算法是把你从你的前置条件带到你的后置条件的工作。在这种情况下，二进制搜索。

score 0 · Accepted Answer

最初的问题假定您正在对数据集合使用二进制搜索。情况并非总是如此。很多时候，您只是想在某个时间间隔内计算一个数字。

假设您正在尝试计算风扇的最佳速度设置。由于某种原因，您找不到封闭形式的表达式，因此您模拟了不同速度设置下的气流。

假设风扇可以从 0RPM 到 5000RPM 的任何速度运行，您实际上不必生成可能速度的列表。您只需在二进制搜索的每个步骤中找到先前最小值和最大值的平均值。