Jump search

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 "L""km", where k in mathbb{N} 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 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 JumpSeach 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" &larr; 0 "b" &larr; &lfloor;&radic;"n"&rfloor; while "L"min("b","n")-1 < "s" do "a" &larr; "b" "b" &larr; "b" + &lfloor;&radic;"n"&rfloor; if "a" &ge; "n" then return nothing while "L""a" < "s" do "a" &larr; "a" + 1 if "a" = min("b","n") return nothing if "L""a" = "s" then return "a" else return nothing

ee also

* Jump list
* Interpolation search
* Linear search - runs in O("n") time, only looks forward
* Binary search - runs in O(log "n") time, looks both forward and backward

References

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Search for Tomorrow — Series title card from December 23, 1981 to February 25, 1986 Genre Soap opera Created by …   Wikipedia

  • Search and rescue dog — The use of dogs in search and rescue (SAR) is a valuable component in responding to law enforcement requests for missing people. Dedicated handlers and hard working, well trained dogs are required in search efforts to be effective in their task.… …   Wikipedia

  • Jump (Madonna song) — Infobox Single Name = Jump Artist = Madonna from Album = Confessions on a Dance Floor Format = CD single, 12 vinyl, 12 picture disc digital single Released = October 31 2006 (Canada) November 3, 2006 (IT, NL, IE) November 6, 2006 (UK and other… …   Wikipedia

  • Search Guard Successor Foundation — The SGS Foundation Logo GoGo Sentai Boukenger (and Daikenjin Zubaan) The Sea …   Wikipedia

  • Jump list — In computer science, a jump list is a data structure which resembles an ordered doubly linked list. Instead of only next and previous links, several nodes contain links to nodes farther away, with the distance increasing geometrically. This… …   Wikipedia

  • Cuckoo search — (CS) is an optimization algorithm developed by Xin she Yang and Suash Deb in 2009.[1][2] It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds (of other species). Some host… …   Wikipedia

  • Water Jump Summer Tour — Cette page a été supprimée. Le journal des suppressions et des déplacements est affiché ci dessous pour référence. 6 octobre 2009 à 21:05 David Berardan (discuter | contributions) a supprimé « Water Jump Summer Tour » ‎ (Décision PàS) Wikipédia… …   Wikipédia en Français

  • Over (Hey! Say! JUMP song) — OVER Single by Hey! Say! JUMP A side OVER B side Aiing Aishiteru …   Wikipedia

  • Maestro! Jump in Music — Developer(s) Pastagames, Neko Entertainment Publisher(s) …   Wikipedia

  • Video search engine — A video search engine is a web based search engine which crawls the web for video content. Some video search engines parse externally hosted content while others allow content to be uploaded and hosted on their own servers. Some engines also… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”