Jump search, explained

Jump search works on a sorted list. Instead of checking every item, it jumps ahead by a fixed number of positions, usually about the square root of the list length, until it passes the target.

Then it goes back to the block it just skipped and scans that block one item at a time.

How it works

• Choose a block size, usually about the square root of the list length.
• Jump from block to block until you reach one whose last item is at least the target.
• Scan that block from the left, one item at a time.
• If you find the target, stop. If the block does not contain it, the target is not in the list.

A small example

Search for 23 in this sorted list of 10 items:

2 5 8 12 16 23 38 56 72 91

The block size is about 3. The search jumps to 8 (too small), then to 23 (big enough, so the jumping stops). It then goes back and scans 12 and 16 and finds 23. Total:

4 checks

Linear search needed 6 checks and binary search needed 3. On a much longer list, the gap between jump search and linear search grows quickly.

What to know about its cost

• Average and worst case O(√n).
• Uses O(1) extra space.
• Needs a sorted list.

Where it works well

• Faster than linear search on large sorted lists.
• Only moves forward, which suits data that is slow to read backwards.

Where it struggles

• Slower than binary search.
• Needs a sorted list.

Try it yourself

Open the Searching experiment, enter the list from this post, set the target to 23, choose Jump Search and step through it. Then compare it with the other algorithms and look at how many positions each one checks.

Open the Searching experiment