Jump Search
Jump sqrt(n) at a time while the block's last value is below the target, then scan one block.
Decision · step 2 of 7Search Variants: Jump search in blocks of 3
Block 0 to 2 ends with 8. That is below 56, so the target cannot be in this block: jump on.
What you will see
A pointer leaps block to block, overshoots, then walks back one cell at a time.
Cost
| Best | O(1) |
|---|---|
| Average | O(sqrt(n)) |
| Worst | O(sqrt(n)) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Cells announce index, value and state (current, discarded, found); each step announces the comparison and the resulting range.
Reduced motion: Range and pointer changes snap into place with a short crossfade; discarded cells fade without movement.
Before this
Related
Taught by the same lesson
Search Variants covers these too, in the same run.