Přejít na vyhledávání - Jump search

v počítačová věda, a skočit vyhledávání nebo blokovat vyhledávání označuje a vyhledávací algoritmus pro seřazené seznamy. Funguje to tak, že nejprve zkontrolujete všechny položky Lkm, kde a m je velikost bloku, dokud není nalezena položka, která je větší než vyhledávací klíč. Vyhledání přesné polohy vyhledávací klávesy v seznamu a lineární vyhledávání se provádí na podseznam L[(k-1)m, km].

Optimální hodnota m je √n, kde n je délka seznamu L. Protože oba kroky algoritmus podívejte se, nanejvýš, √n položky, které algoritmus běží v O (√n) čas. To je lepší než a lineární vyhledávání, ale horší než a binární vyhledávání. Výhodou oproti tomu druhému je, že vyhledávání skoků musí skákat dozadu pouze jednou, zatímco binární soubor může skákat dozadu nahoru a přihlásit n krát. To může být důležité, pokud skok dozadu trvá podstatně více času než skok vpřed.

Algoritmus lze upravit provedením několika úrovní skokového vyhledávání v podřízených seznamech, než se konečně provede lineární vyhledávání. Pro k- skok na úrovni hledá optimální velikost bloku ml pro l th úroveň (počítáno od 1) je n(k-l) / k. Upravený algoritmus bude fungovat k dozadu skáče a běží v O (kn1/(k+1)) čas.

Implementace

algoritmus Přejít na vyhledávání je    vstup: Objednaný seznam L, jeho délka n a vyhledávací klíč s.    výstup: Pozice s v Lnebo nic -li s není v L.        A ← 0    b ← ⌊√n⌋        zatímco Lmin (b,n)-1 < s dělat        A ← b        b ← b + ⌊√n⌋        -li A ≥ n pak            vrátit se nic        zatímco LA < s dělat        A ← A + 1        -li A = min (b, n)            vrátit se nic        -li LA = s pak        vrátit se A    jiný        vrátit se nic

Viz také

Reference

  • Tento článek zahrnuje public domain materiál zNIST dokument:Černý, Paul E. „skokové vyhledávání“. Slovník algoritmů a datových struktur.
  • Ben Shneiderman, Skokové vyhledávání: Technika rychlého sekvenčního vyhledávání, CACM, 21 (10): 831-834, říjen 1978.