jump search

(algorithm)

Definition: Search a sorted array by checking every j^th item until the right area is found, then doing a linear search. The optimum for n items is when j=√ n.

Also known as block search.

Generalization (I am a kind of ...)
search.

See also interpolation search, binary search, linear search.

Note: If there will be two levels of jumping, the optimum is j=n^2/3 for the first jumps and j=n^1/3 for the second level of jumps.

Author: PEB

More information

Ben Shneiderman, Jump Searching: A Fast Sequential Search Technique, CACM, 21(10):831-834, October 1978.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 3 September 2019.
HTML page formatted Fri Sep 6 15:26:10 2019.

Cite this as:
Paul E. Black, "jump search", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 3 September 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/jumpsearch.html