Definition: Search a sorted array by checking every jth 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 ...)
See also interpolation search, binary search, linear search.
Note: If there will be two levels of jumping, the optimum is j=n2/3 for the first jumps and j=n1/3 for the second level of jumps.
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 E. Black.
Entry modified 8 March 2004.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "jump search", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 8 March 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/jumpsearch.html