How can Jump Search be improved?

Concept: Jump Search is a technique for a sorted array that trades some comparisons for large forward jumps: pick a step size k, and check the value at index k-1, 2k-1, 3k-1, and so on, until the first block whose last checked index is greater than or equal to the target is found. A confirming linear scan then pins down the exact match inside just that block. Because the worst case needs about n/k jumps plus up to (k-1) scan comparisons, exactly where that confirming scan starts affects the total work.

Application:

1. Suppose the array has 16 sorted elements and the chosen step size is k = 4 (close to root 16). The algorithm first compares the target against the value at index 3 (position k-1, the end of the first block).

2. Say that value is still less than the target - the first block is ruled out, and the boundary the jump phase has reached becomes index k (=4). The next jump then compares the target against the value at index 7 (position 2k-1, the end of the second block).

3. Say the value at index 7 is greater than or equal to the target - the target lies in the block spanning indices 4 to 7, which begins exactly at index k, the boundary the jump phase already reached.

4. The confirming scan should now begin at index k (=4), not at index 0: indices 0 through 3 were already ruled out by the first jump, so re-checking them would waste comparisons. This is exactly what beginning the scan from the kth item means, and for a block found even further along, the same rule applies at the matching multiple of k.

Cross-check: One case needs care: when the target is found in the very first block (the very first jump already succeeds), no earlier jump has ruled anything out yet, so the confirming scan there genuinely must start at index 0 - the kth-item optimization only applies from the second block onward, exactly as illustrated above. This detail does not change the overall time complexity: total comparisons are still on the order of n/k + (k-1), minimized exactly when k equals root n (found by setting the derivative of n/k + k to zero). Skipping the region already ruled out removes only redundant comparisons, which is why the gain is called a very slight improvement rather than a change to the complexity class. Reversing the scan direction changes nothing about how many blocks are inspected, and moving the step size away from root n increases the worst-case comparison count instead of reducing it.