二分搜索

Question

所以，我想了解更多关于二进制搜索的知识，因为我并不是真的理解。二进制搜索需要一个前提条件，即数组是排序的。我没记错吧？似乎一个方法应该检查这个前提条件，如果不满足就抛出一个异常。但是，为什么检查前提条件是一个坏主意？

Answer 1

这不是一个好主意，因为检查数据是否排序需要n步骤。整个搜索都是关于log(n)步骤的。

如果你要检查，你最好做一个线性搜索。

Answer 2

二进制搜索的全部意义在于，由于数据已经排序，您可以快速找到所需的信息。

拿电话簿来说，电话簿是按姓氏排序的。

你如何在电话簿中找到某人？你打开它，打开一个你认为会接近你想要的页面，然后开始翻页。

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

这就是二进制搜索所做的事情。由于数据是经过排序的，它知道可以跳过很多次并进行另一次查看，然后它会专注于您想要的信息。

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

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

因此，如果不能保证数据是排序的，就不应该使用二进制搜索，因为它的性能将优于简单的扫描。

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

Answer 3

是的，二分搜索涉及0(log )个步骤，而验证整个序列是否排序涉及0(n)个步骤。从我的观点来看，最好在调试模式下验证它，而不是在发布期间。