algorithm - 二分查找在遍历成本方面效率不高。什么是？

Question

当我试图将二分搜索应用于现实世界时，它让我失望了。场景如下。

I need to test the range of a device that communicates over radio. Communication needs to occur quickly, but slow transmission is tolerable, up to a point (say, about 3 minutes). I need to test whether transmissions will be successful every 200 feet until failure, up to 1600 feet. Every 200 feet a test will be run which requires 3 minutes to execute.

我天真地假设二分查找是找到故障点的最有效方法，但考虑到 200 英尺/分钟的行进速度和 3 分钟的测试时间。如果传输失败发生在 500 英尺处，二分查找不是查找故障点的最有效方法，如下所示。

简单地向前走并测试每个点会更快地找到解决方案，只需 12 分钟，而二进制搜索和测试将需要 16 分钟。

我的问题:当旅行时间很重要时，您如何计算最有效的解决方案路径？这叫什么(例如，二进制旅行搜索等)？

Answer 1

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

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

现在您实际上可以进行二分查找了，从 2<sup>i-2</sup>x 开始.从那里，你可以向前或向后走，但你一定会旅行2<sup>i-3</sup>x ，下一次迭代你将旅行 2<sup>i-4</sup>x , 等等。

总而言之，在第一阶段(搜索最大值)，您走到了2<sup>i</sup>x。 ，并做了 i测试。在第二阶段，二进制细化，你总共走 (2<sup>i-1</sup>-1)x并做 i-1测试。你会在某个时候结束 d在 2<sup>i-1</sup> 之间和 2<sup>i</sup> ，所以在最坏的情况下你会走路3d最后一点(充其量，您将步行 3d/2 )。您将完成的测试数量将为 2*ceil(log<sub>2</sub>(d/x)) - 1 ，这是在 2*log<sub>2</sub>(d/x) 的一次测试中.

那么什么情况下应该做二分查找算法呢？基本上，这取决于旅行时间与测试时间的比率，以及所需的答案精度。简单的顺序算法找到位置 d在 d/x 之后大小移动 x和 d/x测试；上面的二进制搜索算法找到位置 d最多旅行后3d但只做 2 log(d/x)测试。粗略地说，如果一次考试的花费是旅行费用的两倍多d/x , 并且期望的距离比精度足够大，你应该更喜欢二分查找。

在您的示例中，您似乎想要精度为 200 英尺的结果；行车时间为1分钟，测试时间为3分钟，是行车时间的两倍多。所以你应该更喜欢二进制搜索，除非你期望答案会在精度的小数倍数中找到(情况就是这样)。请注意，尽管二进制算法使用四次测试和 1000 英尺的行程(与顺序算法的三次测试和 600 英尺相比)，将精度提高到 50 英尺只会增加四次测试和 150 英尺的行程到二进制算法，而顺序算法将需要 20 次测试。

---

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