Jump search
Jump search checks the last value of successive fixed-size blocks, advancing block by block until it finds one whose end is not smaller than the target, then scans that block one value at a time. It requires the array to be sorted first, and uses a block size equal to the square root of the array's length.
When it is the right choice
Jump search is a reasonable middle ground when random-access jumps (as binary search makes) are more expensive than sequential access, for instance stepping through a structure that is fast to scan forward but slow to seek within. For a plain in-memory array, binary search's O(log n) is strictly better than jump search's O(√n), so jump search is mainly of interest for what it demonstrates about trading comparisons for simplicity.
How it works
- Set the block size to the square root of the array length.
- Compare the last value of the current block with the target.
- If that value is smaller than the target, the target cannot be in this block, so jump ahead to the next block.
- Once a block's end is not smaller than the target, the target might be in that block, so step through it one value at a time from its start.
- If a value along the way matches, the target is found.
- If the last block is exhausted without a match, the target is not in the array.
Worth noticing
- Its O(√n) worst case sits between linear search's O(n) and binary search's O(log n) — it is never the fastest option on a plain in-memory array, only a useful stepping stone for understanding the trade-off.
- Choosing a block size other than √n changes its performance: too small approaches linear search, too large means more work scanning within each block.
Cost
- Best
- O(1)
- Average
- O(√n)
- Worst
- O(√n)
- Extra space
- O(1)