1. Jump size
Use about square root of n as the block size.
Math.floor(Math.sqrt(arr.length))Typorithm · medium
Jump Search
▷ Interactive algorithm labjump-searchsearchsorted-arrayblockssquare-root-time
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Jump Search
Search Algorithms
Jump Search skips through a sorted array by blocks, then linearly scans the one block that could contain the target.
Jump Search assumes the array is sorted.
It checks the last value of each block to skip ranges that are too small.
Once the target could be inside a block, it scans that block one item at a time.
A square-root block size balances jumping and scanning work.
Preparing algorithm lab…
01
Requires sorted input.
02
Jump by sqrt(n) sized blocks.
03
Use block end values to skip ranges.
04
Scan only the candidate block.
05
Time is O(sqrt n).
function jumpSearch(arr, target) {
const jump = Math.floor(Math.sqrt(arr.length));
let start = 0;
let end = jump;
while (start < arr.length && arr[Math.min(end, arr.length) - 1] < target) {
start = end;
end += jump;
}
for (let i = start; i < Math.min(end, arr.length); i++) {
if (arr[i] === target) return i;
}
return -1;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Block start
start marks the beginning of the current block.
let start = 03. Skip block
If the block's last value is still too small, the target cannot be inside it.
arr[Math.min(end, arr.length) - 1] < target4. Advance block
Move to the next block after skipping this one.
start = end5. Scan block
After finding the possible block, scan inside it linearly.
for (let i = start; i < Math.min(end, arr.length); i++)6. Return match
Return the index when the target is found inside the block.
if (arr[i] === target) return iA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.