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 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 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 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 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

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.

Read other articles:

Yuyun Wahyuningrum

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2022. Wahyuningrum atau lebih dikenal sebagai Yuyun Wahyuningrum (lahir di Jakarta, 7 Januari 1973)[1] adalah perempuan pembela HAM yang aktif menyuarakan keadilan di tingkat ASEAN melalui organisasi Human Rights Working Group (HRWG) di mana ia beke...

Kepulauan Utara

Peta lokasi Kepulauan Utara Skotlandia. Kepulauan Utara (Inggris: Northern Islescode: en is deprecated ; Scots: Northren Islescode: sco is deprecated ; bahasa Gaelik Skotlandia: Na h-Eileanan a Tuath; bahasa Nordik Kuno: Norðreyjar) adalah serangkaian kepulauan di sebelah utara daratan Skotlandia. Iklim di kepulauan ini dingin dan sedang, dan dipengaruhi oleh laut di sekeliling. Terdapat dua kepulauan utama, yaitu Shetland dan Orkney. Orkney memiliki lanskap agrikultural yang subur, ...

Pengemasan

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Pengemasan – berita · surat kabar · buku · cendekiawan · JSTOR Contoh Kemasan Pengemasan merupakan sistem yang terkoordinasi untuk menyiapkan barang menjadi siap untuk diangkutkan, diagihkan, disimpan, dijual...

John Goodall

British footballer This article is about the English footballer and cricketer. For the British artist and illustrator, see John S. Goodall. For the architectural historian, see John Goodall (author). For the Australian ice hockey player, see John Edwin Goodall. For the English Tory politician, see John Goodall (MP). John Goodall 1889 sketch of GoodallPersonal informationDate of birth (1863-06-19)19 June 1863[1]Place of birth Westminster, London, England[2]Date of death 20 May ...

2000 United States Senate election in Michigan

2000 United States Senate election in Michigan ← 1994 November 7, 2000 2006 → Nominee Debbie Stabenow Spencer Abraham Party Democratic Republican Popular vote 2,061,952 1,994,693 Percentage 49.47% 47.86% County results Municipality resultsStabenow: 40–50% 50–60% 60–70% 70–80% 80–90% ...

بيدرو إيمانويل

بيدرو إيمانويل معلومات شخصية الميلاد 11 فبراير 1975 (العمر 49 سنة)لواندا الطول 1.80 م (5 قدم 11 بوصة) مركز اللعب مدافع الجنسية البرتغال معلومات النادي النادي الحالي الخليج (مدرب) مسيرة الشباب سنوات فريق 1986–1993 بوافيشتا المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1993–1994 ...

Tamar (album)

2000 studio album by Tamar BraxtonTamarStudio album by Tamar BraxtonReleasedMarch 21, 2000 (2000-03-21)Recorded1999Length60:37Label DreamWorks RedZone Producer Tim & Bob Shane August Jermaine Dupri Missy Elliott Christopher Tricky Stewart Darrell Delite Allamby Tamar Braxton chronology Tamar(2000) Love and War(2013) Singles from Tamar Get NoneReleased: October 5, 1999[1] If You Don't Wanna Love MeReleased: March 7, 2000[2] Tamar is the debut studio a...

Gunn-Rita Dahle Flesjå

Norwegian cyclist This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (January 2014) (Learn how and when to remove this template message) Gunn-Rita Dahle FlesjåDahle Flesjå in 2016Personal informationFull nameGunn-Rita Dahle FlesjåNicknameCat Woman, The Iron Woman, Mountain-bike QueenBorn (1973-02-10) 10 February 1973 (age 51)Stavanger, NorwayHeight17...

Puchar Polski 2015-2016

Puchar Polski 2015-2016 Competizione Puchar Polski Sport Calcio Edizione 62ª Organizzatore PZPN Date dal 18 luglio 2015al 2 maggio 2016 Luogo Polonia Partecipanti 68 Risultati Vincitore Legia Varsavia(18º titolo) Secondo Lech Poznań Cronologia della competizione 2014-2015 2016-2017 Manuale La Puchar Polski 2015-2016 è stata la 62ª edizione della coppa nazionale polacca, organizzata dalla PZPN. La competizione è iniziata il 18 luglio 2015 e si è conclusa il 2 ...

René Hamel

Questa voce sull'argomento ciclisti francesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. René Hamel Nazionalità Francia Ciclismo Specialità Ciclismo su strada Palmarès Competizione Ori Argenti Bronzi Giochi olimpici 1 0 1 Per maggiori dettagli vedi qui Modifica dati su Wikidata · Manuale René Nicolas Adrien Hamel (Orša, 14 ottobre 1902 – Gouvieux, 7 novembre 1992[1 ...

Prunus campanulata

Species of tree Taiwan cherry Prunus campanulata blossoms Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Rosids Order: Rosales Family: Rosaceae Genus: Prunus Subgenus: Prunus subg. Cerasus Section: P. sect. Cerasus Species: P. campanulata Binomial name Prunus campanulataMaxim.[1] Synonyms[2][3] Cerasus campanulata (Maxim.) A.Vassiliev Prunus cerasoides var. campanulata (Maxim.) Koidz. Prunus pendula hort. ...

卡洛斯·梅内姆

此條目需要擴充。 (2015年11月27日)请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。卡洛斯·梅内姆阿根廷總統府官方照片第47任阿根廷總統任期1989年7月8日—1999年12月10日副总统爱德华多·杜阿尔德卡洛斯·鲁考夫（英语：Carlos Ruckauf）前任劳尔·阿方辛个人资料出生(1930-07-02)1930年7月2日阿根廷拉里奥哈省阿尼利亚�...

Хип-хоп

Хип-хоп Направление популярная музыка Истоки фанкдискоэлектронная музыкадабритм-энд-блюзреггидэнсхоллджаз[1]чтение нараспев[англ.]исполнение поэзииустная поэзияозначиваниедюжины[англ.]гриотыскэтразговорный блюз Время и место возникновения Начало 1970-х, Бронкс, Н...

The Show-Off

For other uses, see The Show-Off (disambiguation). 1924 play The Show-OffFirst edition dust jacket featuring Louis John Bartels in the original Broadway productionWritten byGeorge KellyDate premieredFebruary 5, 1924 (1924-02-05)Place premieredPlayhouse TheatreNew York CityOriginal languageEnglishGenreComedy The Show-Off is a 1924 stage play by George Kelly about a working-class North Philadelphian family's reluctance to accept their daughter's suitor Aubrey Piper, an overly con...

Louis Rostollan

Questa voce o sezione sull'argomento ciclisti francesi non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Louise RostollanNazionalità Francia Ciclismo SpecialitàStrada Termine carriera1967 CarrieraSquadre di club 1955 Rochet1956 Liberia La Perle1957 Liberia1958 LiberiaEssor195...

Ancient history

Human history between prehistory and the Medieval period This article is about history from the beginning of writing. For earlier periods, see Prehistory. For other uses, see Ancient history (disambiguation). Ancient and Ancient World redirect here. For the TV series, see The Ancient World (TV series). For other uses, see Ancient (disambiguation). Well-known ancient artworks, each representing a certain civilisation. From left to right: the Standard of Ur (Sumerian), the Mask of Tutankhamun (...

Mary Thurman

Mary ThurmanThurman pada 1924LahirMary Christiansen(1895-04-27)27 April 1895Richfield, Utah, Amerika SerikatMeninggal22 Desember 1925(1925-12-22) (umur 30)New York City, Amerika SerikatMakamRichfield City CemeteryPendidikanUniversitas UtahPekerjaanPemeran, peraga busanaTahun aktif1915–1925Suami/istri Victor E. Thurman (m. 1915; bercerai 1919) Mary Thurman (née. Christiansen, 27 April 1895 – 22 Desember 1925) ada...

Nikadin (archaeological site)

Cultural heritage monument of Kosovo This majority of content of this article, if not all may have been copied and pasted from another location, possibly in violation of Wikipedia's copyright policy. Please review the source and remedy this by editing this article to remove any non-free copyrighted content and attributing free content correctly, or flagging the content for deletion. Please be sure that the supposed source of the copyright violation is not itself a Wikipedia mirror. (October 2...

Fedayeen Saddam

Ba'athist Iraqi paramilitary organization This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Fedayeen Saddam – news · newspapers · books · scholar · JSTOR (November 2009) (Learn how and when to remove this message) Fedayeen Saddamفدائيي صدامFedayeen Saddam shoulder sleeve insigniaFounded1995 (199...

Universitas Adelaide

Universitas AdelaideThe University of Adelaidebahasa Latin: universitas adelaide Tampilkan peta yang diperbesarTampilkan peta yang diperkecil InformasiMotoSub Cruce Lumenbahasa Inggris: The light (of learning) under the (Southern) Crossbahasa Indonesia: Lampu (belajar) di bawah Salib (Selatan)JenisPublikDidirikan1874KanselirThe Hon. Rear Admiral Kevin Scarce AC, CSCPresidenProfesor Peter RathjenStaf administrasi3.159Jumlah mahasiswa25.000LokasiAdelaide, Australia Sel...

PROFILPELAJAR.COM