This HTML5 document contains 39 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n11https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-thhttp://th.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Jump_search
rdf:type
yago:YagoPermanentlyLocatedEntity yago:Abstraction100002137 yago:Activity100407535 yago:Algorithm105847438 yago:PsychologicalFeature100023100 yago:Rule105846932 yago:WikicatSearchAlgorithms yago:Act100030358 yago:Event100029378 yago:Procedure101023820
rdfs:label
Jump search
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].
dcterms:subject
dbc:Search_algorithms
dbo:wikiPageID
2569382
dbo:wikiPageRevisionID
1041475777
dbo:wikiPageWikiLink
dbr:Search_key dbr:Skip_list dbr:Binary_search dbr:Linear_search dbr:Ben_Shneiderman dbr:Algorithm dbr:Sublist dbc:Search_algorithms dbr:List_(computing) dbr:Computer_science dbr:Search_algorithm dbr:Interpolation_search
owl:sameAs
dbpedia-fa:جستجوی_پرشی dbpedia-th:การค้นหาแบบกระโดด n11:4ZYUj wikidata:Q4922513 freebase:m.07nnlv yago-res:Jump_search
dbp:wikiPageUsesTemplate
dbt:DADS dbt:Radic
dbo: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.
prov:wasDerivedFrom
wikipedia-en:Jump_search?oldid=1041475777&ns=0
dbo:wikiPageLength
2626
foaf:isPrimaryTopicOf
wikipedia-en:Jump_search