Jump Search

On sorted data, hops forward in fixed-size blocks of √n until it overshoots the target, then walks back through the final block with a linear scan. A middle ground between linear and binary search.

Best

O(1)

Average

O(√n)

Worst

O(√n)

Space

O(1)