“Jump search”的意思、由来-开放百科全书

词条

Jump search

释义

Implementation
See also
References

In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items L_km, 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 {{radic|n}}, where n is the length of the list L. Because both steps of the algorithm look at, at most, {{radic|n}} items the algorithm runs in O({{radic|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 a 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 an k-level jump search the optimum block size m_l 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(kn^1/(k+1)) time.

Implementation

 '''Algorithm''' JumpSearch   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''' ''L''_{min(''b'',''n'')-1} < ''s'' '''do'''     ''a'' ← ''b''     ''b'' ← ''b'' + ⌊√''n''⌋     '''if''' ''a'' ≥ ''n'' '''then'''       '''return''' '''nothing'''    '''while''' ''L''_''a'' < ''s'' '''do'''     ''a'' ← ''a'' + 1     '''if''' ''a'' = min(''b'',''n'')       '''return''' '''nothing'''    '''if''' ''L''_''a'' = ''s'' '''then'''     '''return''' ''a''   '''else'''     '''return''' '''nothing'''

References

{{DADS|jump search|jumpsearch}}
Ben Shneiderman, Jump Searching: A Fast Sequential Search Technique, CACM, 21(10):831-834, October 1978.

1 : Search algorithms

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Implementation

See also

References