Skip to content
Back to AlgorithmsAll lessons

Algorithms

Jump Search

O(sqrt n) time — far fewer checks than linear search, though more than binary search's O(log n) · O(1) space.

The idea, in plain English

Jump search flips through a phone book in big chunks instead of one page at a time. You jump ahead by a whole block of pages. As soon as you go past the name you want, stop and search that one block page by page. This only works if the data is sorted first.

How it works

  1. 1Pick a block size. This is usually the square root of the list's length.
  2. 2Jump ahead by that many items at a time, until you land on a block that could hold the target.
  3. 3Search inside that one block, item by item, to find the exact match.

When you'd use it

Use it to search a large sorted list when jumping backward is expensive, like on a tape or slow storage. It sits between linear search and binary search in speed.

Common beginner mistakes

  • Running it on unsorted data. Like binary search, it needs the list to be sorted first.
  • Letting the block position run past the end of the list, instead of stopping it there.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Index of 23: 4
Index of 10: -1

See it in motion

Watch it searchJump searchTarget 8O(sqrt n) time — far fewer checks than linear search, though more than binary search's O(log n) · O(1) space.

Sorted first — jump search only works on ordered data.

Ready. Press play to hunt for the target.

0
Comparisons
—
Result
0/6
Step
0.0s
Time
CheckingIn rangeRuled outFound

Not sure this is the right topic? See the learning paths → or where this leads →