二进制搜索

题

因此，我想更多地了解二进制搜索，因为我不太了解。二进制搜索需要对数组进行排序的先决条件。我明白了吗？似乎一种方法应该检查此前提条件并在不满足的情况下引发例外。但是，为什么检查前提是一个坏主意？

解决方案

这是一个坏主意，因为检查数据已排序 n 脚步。整个搜索是关于 log(n) 脚步。
如果要检查，您不妨进行线性搜索。

其他提示

二进制搜索的全部要点是，由于已经对数据进行了排序，因此您可以快速找到所需的信息。

取电话书，用姓氏排序。

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

但是，您不会每次都翻转一页，如果您错过了很多东西，您会翻转一堆页，然后最后一次开始翻转一个页面，直到最终开始查看一页。

这就是二进制搜索所做的。由于数据已排序，因此它知道它可以跳过很多，然后再看一下，并且会重点关注您想要的信息。

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

如果您在运行实际的二进制搜索之前，请进行完整的操作以检查数据是否已排序，则可能只需扫描信息即可。完整的直通 +二进制搜索将需要n + log2 n操作，因此，对于1024个元素，它需要大约1034个比较，而对信息的简单扫描平均需要一半，即512。

因此，如果您不能保证数据已排序，则不应使用二进制搜索，因为简单扫描的表现将胜过。

编辑: ：我会这么说，您可以添加一个仅调试代码步骤来验证此步骤，以捕获本应准备二进制搜索数据的代码中的错误，但是知道，由于我上面写的内容，这将使总运行时间大得多，因此根据您想做的检查，您可能想或不想添加它。但是它不应在发行代码中存在。

是的，二进制搜索涉及0（log n）步骤，并且对整个序列进行排序涉及0（n）步骤。从我的角度来看，最好以调试模式而不是在发布过程中对其进行验证。

二进制搜索假设输入数据已排序。所以你在这里是正确的。

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

更多细节。