About: Jump search

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Jump search Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Rule105846932, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FJump_search&invfp=IFP_OFF&sas=SAME_AS_OFF

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 . To find the exact position of the search key in the list a linear search is performed on the L[(k-1)m, km].

Attributes	Values
rdf:type	yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:label	Jump search (en)
rdfs:comment	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 . To find the exact position of the search key in the list a linear search is performed on the L[(k-1)m, km]. (en)
dcterms:subject	Search algorithms
Wikipage page ID	2569382 (xsd:integer)
Wikipage revision ID	1041475777 (xsd:integer)
Link from a Wikipage to another Wikipage	Ben Shneiderman Algorithm Interpolation search Search algorithms Linear search Computer science Search algorithm Skip list List (computing) Binary search dbr:Search_key dbr:Sublist
sameAs	Jump search Jump search Jump search Jump search Jump search Jump search
dbp:wikiPageUsesTemplate	dbt:DADS dbt:Radic
has abstract	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 . To find the exact position of the search key in the list a linear search is performed on the 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 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. (en)
prov:wasDerivedFrom	wikipedia-en:Jump_search?oldid=1041475777&ns=0
page length (characters) of wiki page	2626 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Jump_search
is Link from a Wikipage to another Wikipage of	List of algorithms Block searching List of terms relating to algorithms and data structures Block search
is Wikipage redirect of	Block searching Block search
is foaf:primaryTopic of	wikipedia-en:Jump_search

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software