AlgoScope

Jump Search

Jump sqrt(n) at a time while the block's last value is below the target, then scan one block.

Searching, algorithm, intermediate
Block ending at index 2 holds 8: jump.active 0-2205182123164235386567728919probe8 < 56
Block ending at index 2 holds 8: jump.active 0-2205182123164235386567728919probe8 < 56

Search Variants: Jump search in blocks of 3

Decision, step 2 of 7

Block 0 to 2 ends with 8. That is below 56, so the target cannot be in this block: jump on.

Cost

Best
O(1)
Average
O(sqrt(n))
Worst
O(sqrt(n))
Space
O(1)

Taught by the same lesson

Search Variants covers these too, in the same run.