# Jump Search visualised: O(√n) between linear and binary search

> Interactive Jump Search: jumps through a sorted array in √n strides and then scans the right block linearly. A sweet spot between O(n) and O(log n).

Address: https://marckimmel.de/en/informatik/suchalgorithmen/jump-suche
Deutsche Fassung: https://marckimmel.de/informatik/suchalgorithmen/jump-suche.md

Jumps through a sorted array in √n strides and scans the right block linearly.

Jump Search is a search method for sorted arrays with random access. Instead of probing every element like linear search or halving the range like binary search, Jump Search advances in fixed strides of size √n. At each jump position it checks whether the element is already ≥ target. As soon as that holds, a linear backward scan walks through the last block (the √n elements since the previous jump). This yields O(√n) runtime in average and worst case, between linear O(n) and binary O(log n). Memory stays constant at O(1). The array must be sorted.

Useful when binary search is awkward because jumping is expensive (e.g. tape storage with high seek costs or sorted structures whose middle is hard to compute) but sequential traversal is cheap. Rare in practice, but relevant in teaching and in some embedded use cases as a compromise O(√n) search.

## Related

- [Search Algorithms](https://marckimmel.de/en/informatik/suchalgorithmen.md)