Question

How can Jump Search be improved?

(a) Start searching from the end

(b) Begin from the kth item, where k is the step size

(c) Cannot be improved

(d) Step size should be other than sqrt(n)

This question was addressed to me in final exam.

This intriguing question comes from Uniform Binary Search topic in portion Searching of Data Structures & Algorithms II

Answer 1

Correct choice is (b) Begin from the kth item, where k is the step size

Explanation: This gives a very slight improvement as you are skipping the first k elements.