When Jump Search is a better alternative than a Binary Search?

Technology CommunityCategory: SearchingWhen Jump Search is a better alternative than a Binary Search?
VietMX Staff asked 3 years ago

Binary Search has a better time complexity (O(log n)) than Jump Search (O(√n)), 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.

For examples where traversing backward could be more expensive, think of data that is stored on tapes: when traversing in forward direction, the tape can just keep winding on-and-on while providing data, but with a backward traversal, the tape needs to stop winding forward (this costs time), perform a rewind, and then reverse its direction again (again, this costs extra time). Or take disk drives, where the disk has to go through one complete revolution to arrive at the spot for reading a previous block.