在二分查找中，为什么向后遍历比向前遍历花费更多？

Question

我的问题来自以下段落：

Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be searched is the smallest element or smaller than the smallest). So in a system where binary search is costly, we use Jump Search.

跳转搜索的内容如下：http://geeksforgeeks.org/jump-search/

Answer 1

In binary search, why traverse back cost more than traverse forward?

这不是一个普遍的真理，也不是GeeksforGeeks的名言想要表达的意思。他们想说的是，如果已知(!) 向后遍历由于某些原因比向前遍历更昂贵（与您使用的搜索方法无关），then 跳转搜索或许会成为一个有趣的选择。如果不是，则几乎没有理由考虑该替代方案。

引用的解释可能会改进如下：

Binary Search is better has a better time complexity than Jump Search, but Jump Search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) backward jumps; consider a situation where the element to be searched is the smallest element or smaller than the smallest). So in a system where binary search is costly a backward traversal is more costly than a forward traversal, we might want to use Jump Search.

对于向后遍历可能更昂贵的示例，想想存储在磁带上的数据：当向前遍历时，磁带可以在提供数据的同时继续缠绕，但向后遍历，磁带需要停止向前缠绕（这会花费时间），执行倒带，然后再次反转方向（同样，这会花费额外的时间）。或者以磁盘驱动器为例，磁盘必须经过一整圈才能到达读取前一个块的位置。