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 8 March 2004.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "jump search", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 8 March 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/jumpsearch.html