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

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的引述想要表达的意思。他们想说的是，如果已知(!) 由于某种原因向后遍历比向前遍历更昂贵(与您使用的搜索方法无关)，然后

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

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.

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