Overview
Jump Search skips through a sorted array by fixed block sizes, then linearly scans the block that may contain the target.
CoreSource checked
Jump Search
Searches sorted data by jumping ahead in blocks before scanning a small block.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Beginner
- Family
- Block Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
candidate searchsorted search spacesequential scanblock searchcandidate spacematch testsearch interval
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(sqrt n)
Worst
O(sqrt n)
Space
O(1)
When to Use
- Use Jump Search when you need to skip sorted data in fixed jumps.
- Use it when the input assumptions match the method's model.
- Use it when you need a clear lookup strategy for known input organization.
- Use it when the method's tradeoffs fit the workload.
When Not to Use
- Avoid it when the input cannot be kept sorted cheaply.
- Avoid it when maintaining the required data layout costs more than the lookup saves.
- Avoid it when the required output is not index of target.
What It Does
- Skips sorted data in fixed jumps
- Scans only the likely block
Use Cases
- Searching sorted arrays
- Teaching search tradeoffs
- Simple block-based lookup
Inputs
- Sorted array
- Target value
- Block size
Outputs
- Index of target
- Not-found result
Key Formulas (1)
Block size
step = ⌊√n⌋
step = floor(sqrt(n))Uses a jump size near the square root of the input length to balance jumping and linear scanning.
Pseudocode
- 1.Jump ahead by block size while block end is below the target
- 2.Step back to the start of the candidate block
- 3.Scan the block one item at a time
- 4.Return the target index or not found
Canonical Example
- Input
- values = [2, 5, 8, 12, 16], target = 12
- Output
- index = 3
- Explanation
- Jump Search: The search checks candidate positions until it identifies the target value.
Implementation Notes
- Keep the input contract explicit: Sorted array; Target value; Block size.
- Decide up front whether not-found results return null, -1, false, or an insertion position.
- Search algorithms should define both success and failure semantics.
Common Pitfalls
- A block size near the square root of the input length balances jumps and scanning.
- Handle empty, invalid, and boundary inputs before trusting index of target.
- Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow large jumps followed by a short linear scan.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 4: Jump ahead by block size while block end is below the target
block-jump-searchNotes
Jump Search operates in O(sqrt n) time and O(1) space within the Block Search family. Key governing relation: step = floor(sqrt(n)). Often compared with Binary Search and Linear Search.
Sources (1)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSearching reference for Jump Search's probe strategy, comparison model, and expected or worst-case behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toBinary Search
Jump search and binary search both exploit sorted order but use different probing patterns.
Related Algorithms
Tags
SearchSorted DataLinear Scan