Sam*_*Sam 3 algorithm search binary-search preconditions
所以,我想更多地了解二进制搜索,因为我真的不明白.二进制搜索需要一个数组排序的前提条件.我做对了吗？看起来一个方法应该检查这个前提条件并在不满足时抛出异常.但是,为什么检查前提条件是个坏主意？
这是一个坏主意,因为检查数据是按顺序进行排序的n.整个搜索是关于log(n)步骤.
如果您要检查,您也可以进行线性搜索.
二进制搜索的重点在于,由于数据已经排序,您可以快速找到所需的信息.
拿电话簿,按姓氏排序.
你如何在电话簿中找到某人？您将其打开到一个您认为接近您想要的页面,然后开始翻页.
但是你不是每次都翻页,如果你错过了很多,你翻了一堆页,然后终于开始一次翻页,直到最后你开始看一页.
这就是二分查找的功能.由于数据是经过排序的,因此它知道它可以跳过很多次并进行另一次查看,并且它将专注于您想要的信息.
二进制搜索对每两倍的项目进行1次比较.因此,1024元素集合最多需要大约10次比较才能找到您的信息,或者至少知道它不存在.
如果您在运行实际二进制搜索之前执行完全运行以检查数据是否已排序,那么您也可以只扫描信息.完全运行+二进制搜索将需要N + log2 N个操作,因此对于1024个元素,它将需要大约1034个比较,而对信息的简单扫描平均需要一半,即512.
因此,如果您无法保证数据已排序,则不应使用二进制搜索,因为它将通过简单扫描表现出色.
编辑:我会这样说,你可以添加一个只调试的代码步骤来验证这一点,以捕获应该为二进制搜索准备数据的代码中的错误,但是知道,由于我上面写的内容,这将使总运行时间更高,因此根据您要对此检查执行的操作,您可能想要也可能不想添加它.但它不应该出现在发布代码中.