遍历成本对二进制搜索效率不高.什么是？

Question

当我试图将它应用到现实世界时,二进制搜索让我失望.方案如下.

我需要测试通过无线电通信的设备的范围.通信需要快速进行,但传输速度慢,可达到一定程度(例如,大约3分钟).我需要测试传输是否每200英尺成功一次,直到失败,最多1600英尺.每200英尺将进行一次测试,需要3分钟才能执行.

我天真地认为二元搜索是找到故障点的最有效方法,但考虑到200英尺/分钟的行进速度和3分钟的测试时间.如果在500英尺处发生传输失败,二进制搜索不是找到故障点的最有效方法,如下所示.

只需走路并测试每一个点就可以更快地找到解决方案,只需12分钟,而二进制搜索和测试则需要16分钟.

我的问题:在旅行时间问题上,您如何计算解决方案的最有效途径？这叫什么(例如,二元旅行搜索等)？

Answer 1

二分查找确实基于O(1)访问时间；例如，对链表进行二进制搜索没有什么意义[但请参阅注释 1]，这本质上就是您正在做的事情，因为您似乎假设只有离散间隔才值得测试。如果您正在寻找更准确的答案，您会发现二分搜索允许任意精度，但代价是每一位精度需要进行一次额外的测试。

假设您甚至不知道最大值是多少。那么你就不能先在中间测试，因为你不知道中间在哪里。相反，您可以对极限进行指数搜索（这是一种由内而外的二分搜索）；您首先在 处进行测试x，然后在 处进行测试2x，然后4x直到达到大于最大值的点（信号达不到那么远）。（x是您感兴趣的最小答案；换句话说，如果第一个测试x显示信号未到达，您将停止。）在此阶段结束时，对于某个整数，您将处于 , ，并且你就会知道答案在和之间。2ixi2i-1x2ix

现在您实际上可以进行二分搜索，从向后开始。从那里开始，您可能会向前或向后移动，但您肯定会旅行，并且您将旅行下一次迭代，依此类推。2i-2x2i-3x2i-4x

总而言之，在第一阶段（搜索最大值），您走到，并进行了测试。在第二阶段，即二进制细化，您将进行总计并进行测试。你最终会到达和之间的某个点，所以最坏的情况下你会走到最后一点（最好的情况下，你会走到）。您将完成的测试数量为，在一次测试之内。2ixi(2i-1-1)xi-1d2i-12i3d3d/22*ceil(log2(d/x)) - 12*log2(d/x)

那么什么情况下应该使用二分查找算法呢？基本上，这取决于旅行时间和测试时间的比率，以及所需的答案精度。简单的顺序算法在大小移动d后找到位置并进行测试；上面的二分搜索算法最多在旅行后找到位置，但只在测试周围进行。粗略地说，如果一次测试的成本是旅行成本的两倍以上，并且预期距离远大于精度，那么您应该更喜欢二分搜索。d/xxd/xd3d2 log(d/x)d/x

在您的示例中，您似乎希望结果精度为 200 英尺；行程时间为1分钟，测试时间为3分钟，是行程时间的两倍多。因此，您应该更喜欢二分查找，除非您希望在少量的精度倍数中找到答案（情况就是如此）。请注意，虽然二进制算法使用四次测试和 1000 英尺的行程（与顺序算法的 3 次测试和 600 英尺的行程相比），但将精度提高到 50 英尺只会为二进制算法再增加四次测试和 150 英尺的行程，而顺序算法则需要 20 次测试。

注1：实际上，如果测试成本很高，则精确使用上述算法对链表进行二分搜索可能是有意义的。假设测试的成本与列表中的索引不成正比，则搜索的复杂度将同时用于O(N)线性搜索和二分搜索，但二分搜索将执行O(log N)测试和O(N)步骤，而顺序搜索将执行O(N)测试和O(N)步骤。对于足够大的 N，这并不重要，但对于现实世界大小的 N，这可能很重要。