Jump Search
Jump sqrt(n) at a time while the block's last value is below the target, then scan one block.
Search 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.
Cost
- Best
- O(1)
- Average
- O(sqrt(n))
- Worst
- O(sqrt(n))
- Space
- O(1)
Before this
Related
Taught by the same lesson
Search Variants covers these too, in the same run.