Question

Which of the following false about Jump Search?

(a) Jump Search is better than Linear Search

(b) Useful when jumping back is more costly than jumping forward

(c) Jump Search is worse than Binary Search

(d) Jump search starts from the index 0 even though specified index is k

I got this question in unit test.

This key question is from Uniform Binary Search in chapter Searching of Data Structures & Algorithms II

Answer 1

Correct option is (d) Jump search starts from the index 0 even though specified index is k

Best explanation: Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won’t start searching from index 0.