二分查找

Question

所以，我想更多地了解二分查找，因为我不太理解。二分查找需要一个前提条件，即数组已排序。我理解对了吗？看起来好像该方法应该检查此前提条件，并在未满足时抛出异常。但是，为什么检查前提条件是个坏主意呢？

- Sam

---

作业？谁告诉你检查前提条件是一个坏主意的？ - Martin v. Löwis

重要吗？这是个糟糕的想法。如果您无法保证数据按照二分查找所需的相同顺序排序，那么您不应该使用二分查找。添加前置条件将使其运行速度比简单的端到端扫描信息更慢。 - Lasse V. Karlsen

不，我的老师谈到这个话题时我有些困惑。 ;) - Sam

这里有一个问题，我手上拿着一个数字，你需要找到它，这个数字在1和无穷大之间。你如何找到这个数字？这是一个常见的问题类型。 - DarthVader

这就像二分查找一样，你需要按照以下步骤进行： 1 2 4 8 16 32 .....直到我告诉你范围为止。然后一旦你找到了范围，就可以返回等等。 - DarthVader

Answer 1

这是一个不好的想法，因为检查数据是否已排序需要n个步骤。整个搜索只需要log(n)个步骤。
如果您要检查，最好进行线性搜索。

- Kobi

---

据我所知，SO的政策有点不清楚（也就是说没有政策）；然而，我认为我们应该尽量避免直接给出作业问题的字面答案，而是通过重新表述问题来引导提问者思考正确的方向（在提问者承认这实际上是一道作业题之后）。 - Martin v. Löwis

@Martin请查看http://meta.stackexchange.com/questions/10811/homework-on-stackoverflow。我受够了这种疑神疑鬼的作业问题。这个问题并没有要求预先制定的解决方案，事实上，这正是SO的用途：获取在独自无法解决的问题上的帮助。 - svens

同意svens的观点 - 这是任何讲师或同学都会给出的答案类型。 - carl

Answer 2

二分查找的核心在于，由于数据已经排序，你可以快速定位所需信息。

以电话簿为例，它是按姓氏排序的。如何在电话簿中找到一个人？你打开它，翻到一个你认为接近你想要的页面，然后开始翻页。但如果你错过了很多，你会连续翻动几页，最后再开始一页一页地翻，直到最终只看一页。

这就是二分查找的原理。由于数据已排序，它知道可以跳过很多内容并进行另一次查找，它会聚焦于你想要的信息。

每加倍的项目数量，二分查找就会进行1次比较。因此，1024个元素的集合最多需要约10次比较来查找你的信息，或者至少弄清楚它不在那里。

如果在实际运行二分查找之前，你对数据进行全面遍历以检查其是否已排序，那么你可能会选择直接扫描信息。全面遍历+二分查找将需要N + log2 N次操作，因此对于1024个元素，它将需要大约1034次比较，而简单扫描信息的平均需求量仅为一半，即512次。

因此，如果不能保证数据已排序，则不应使用二分查找，因为简单扫描将比其表现更好。

编辑：虽然你可以添加一个仅用于调试的代码步骤来验证这一点，以捕获准备数据进行二分查找的代码中的错误，但请注意，由于上述原因，这将使总运行时间大大增加，因此根据你想要做什么检查，你可能需要或不需要添加它。但它不应该存在于发布代码中。

- Lasse V. Karlsen

Answer 3

是的，二分查找需要0(log n)步骤，验证整个序列已排序需要0(n)步骤。从我的角度来看，在DEBUG模式下验证它是很好的，而不是在发布时。

- yves Baumes

---

复杂度为O(log(n))，但所需步骤为Floor(Log_2(n))+1。 - Luka Rahne

Answer 4

二分查找假设输入数据已排序。所以在这里你是正确的。

现在一般情况下，检查数据是否已排序需要一些时间。因此，在每次搜索之前执行此操作会使搜索变得非常低效。

更多细节。

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

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

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

而且很容易说出什么时候会出现这种效果。我只是计算了您将花费多少时间进行预检查与实际搜索。

• 对于1个元素，您不需要花费时间搜索。
• 对于2个元素，您需要花费50％的时间进行搜索。
• 对于5个元素，您需要花费46％的时间进行搜索。
• 对于20个元素，您需要花费22％的时间进行搜索。
• 对于100个元素，您需要花费7％的时间进行搜索。

等等。在每种情况下，其余的时间都花费在前置条件检查上。

- Michal Sznajder

Answer 5

除了其他人提到的运行时间（O(n)检查所有项，与O(log(n))运行二分搜索相比），

我认为你误解了前置条件的概念。前置条件和后置条件是一种契约。如果你的前置条件成立，并且你运行你的算法，那么你的后置条件将成立。如果你的前置条件不成立，那么你对后置条件不做任何保证。

因此，基本上，二分搜索说的是：如果你给我的数据已经排序好了，那么我可以通过执行大约log(n)次检查来告诉你特定数据的位置，或者如果不存在，我也可以告诉你。如果数据没有排序，我对我的答案不做任何保证。

从前置条件到后置条件所需的工作就是你的算法。在这种情况下，是二分搜索。

- Rob Rolnick

Answer 6

原始问题假设您正在对数据集执行二分查找。但并非总是如此。很多时候，您只是尝试计算某个区间内的数字。

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

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

- Jørgen Fogh