Jump search

In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items Lkm, where and m is the block size, until an item is found that is larger than the search key. To find the exact position of the search key in the list a linear search is performed on the sublist L[(k-1)m, km].

The optimal value of m is √n, where n is the length of the list L. Because both steps of the algorithm look at, at most, √n items the algorithm runs in O(√n) time. This is better than a linear search, but worse than a binary search. The advantage over the latter is that a jump search only needs to jump backwards once, while a binary can jump backwards up to log n times. This can be important if jumping backwards takes significantly more time than jumping forward.

The algorithm can be modified by performing multiple levels of jump search on the sublists, before finally performing the linear search. For a k-level jump search the optimum block size ml for the l th level (counting from 1) is n(k-l)/k. The modified algorithm will perform k backward jumps and runs in O(kn1/(k+1)) time.

Implementation

 
algorithm JumpSearch is
    input: An ordered list L, its length n and a search key s.
    output: The position of s in L, or nothing if s is not in L.
    
    a ← 0
    b ← ⌊√n⌋
    
    while Lmin(b,n)-1 < s do
        a ← b
        b ← b + ⌊√n⌋
        if a ≥ n then
            return nothing
    
    while La < s do
        a ← a + 1
        if a = min(b, n)
            return nothing
    
    if La = s then
        return a
    else
        return nothing

See also

References
  • Public Domain This article incorporates public domain material from Paul E. Black. "jump search". Dictionary of Algorithms and Data Structures. NIST.
  • Ben Shneiderman, Jump Searching: A Fast Sequential Search Technique, CACM, 21(10):831-834, October 1978.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.