-
21-09-2019 - |
题
因此,我想更多地了解二进制搜索,因为我不太了解。二进制搜索需要对数组进行排序的先决条件。我明白了吗?似乎一种方法应该检查此前提条件并在不满足的情况下引发例外。但是,为什么检查前提是一个坏主意?
解决方案
这是一个坏主意,因为检查数据已排序 n
脚步。整个搜索是关于 log(n)
脚步。
如果要检查,您不妨进行线性搜索。
其他提示
二进制搜索的全部要点是,由于已经对数据进行了排序,因此您可以快速找到所需的信息。
取电话书,用姓氏排序。
您如何在电话簿中找到某人?您将其打开到一个您假设将接近您想要的页面的页面,然后开始翻转页面。
但是,您不会每次都翻转一页,如果您错过了很多东西,您会翻转一堆页,然后最后一次开始翻转一个页面,直到最终开始查看一页。
这就是二进制搜索所做的。由于数据已排序,因此它知道它可以跳过很多,然后再看一下,并且会重点关注您想要的信息。
二进制搜索对每次加倍的项目进行1个比较。因此,1024个元素集合最多需要大约10个比较才能找到您的信息,或者至少发现它不存在。
如果您在运行实际的二进制搜索之前,请进行完整的操作以检查数据是否已排序,则可能只需扫描信息即可。完整的直通 +二进制搜索将需要n + log2 n操作,因此,对于1024个元素,它需要大约1034个比较,而对信息的简单扫描平均需要一半,即512。
因此,如果您不能保证数据已排序,则不应使用二进制搜索,因为简单扫描的表现将胜过。
编辑: :我会这么说,您可以添加一个仅调试代码步骤来验证此步骤,以捕获本应准备二进制搜索数据的代码中的错误,但是知道,由于我上面写的内容,这将使总运行时间大得多,因此根据您想做的检查,您可能想或不想添加它。但是它不应在发行代码中存在。
是的,二进制搜索涉及0(log n)步骤,并且对整个序列进行排序涉及0(n)步骤。从我的角度来看,最好以调试模式而不是在发布过程中对其进行验证。
二进制搜索 假设输入数据已排序。所以你在这里是正确的。
现在,通常检查数据是否已排序。因此,在每次搜索都会使搜索效率低下之前执行此操作。
更多细节。
假设“ n”是您的数据量。
二进制搜索 需要 O(log(n))
在最坏的情况下操作以找到一个元素。确保对数据进行排序需要 O(n)
操作。
因此,如果我们每次都会检查前提条件是否很大 n
与进行实际搜索相比,我们将开始花费大部分时间来检查先决条件。
何时您会看到这种效果,这并不难。我刚刚计算了您将花费多少时间来进行预先搜索与实际搜索
- 对于1个元素,您不花时间搜索。
- 对于2个要素,您花在搜索上50%。
- 对于5个要素,您花在搜索上46%
- 对于20个元素,您花费了22%的搜索。
- 对于100个元素,您花了7%的搜索。
等等。在每种情况下,准时休息都是在先决条件检查上。
除了其他所有人对运行时间(O(n)检查所有项目的说法)外,还与O(log(n))进行二进制搜索。
我认为您误解了前提的想法。条件和后条件是合同。如果您的先决条件是正确的,并且您运行算法,那么您的帖子条件将是正确的。如果您的前提条件是错误的,那么您就不保证在邮局条件下。
因此,基本上,二进制搜索说:如果您给我的数据已经分类,那么我可以通过执行大约log(n)检查来告诉您特定数据的位置,或者如果不存在。如果数据未排序,我不能保证我的答案。
如果您的算法,将您从前提条件到后条件的工作。在这种情况下,二进制搜索。
原始问题以您在数据集合上使用二进制搜索的前提为前提。并非总是如此。很多时候,您只是试图在某个时间间隔内计算一个数字。
假设您正在尝试计算风扇的最佳速度设置。由于某种原因,您找不到封闭的表达式,因此您以不同的速度设置模拟气流。
假设风扇可以从0rpm到5000rpm的任何速度运行,则实际上不必生成可能的速度列表。您只需在二进制搜索的每个步骤中找到前一个最小值和最大值的平均值即可。