Metoda przeszukiwania w uporządkowanych tablicach, która polega na podzieleniu tablicy na kilka części i wykonywaniu wyszukiwania liniowego tylko w tej części, gdzie może znajdować się poszukiwany element, w języku angielskim jest określana jako

Wyjaśnienie

Jump search to faktycznie ta metoda, która polega na przeszukiwaniu uporządkowanej tablicy przez podział jej na bloki o określonej długości (zazwyczaj o rozmiarze pierwiastka kwadratowego z n, gdzie n to liczba elementów w tablicy). Najpierw skaczemy po tych blokach, żeby szybko ograniczyć obszar poszukiwań, a potem wykonujemy liniowe przeszukiwanie już tylko w wybranym przedziale. To sprawia, że jump search jest czymś pomiędzy wyszukiwaniem liniowym a binarnym – daje przyzwoity kompromis między prostotą a wydajnością, szczególnie gdy dostęp do pamięci jest kosztowny albo tablica jest zbyt duża, by od razu dzielić ją na pół jak w binary search. W praktyce jump search czasem się wykorzystuje tam, gdzie dane są przechowywane na przykład na dyskach magnetycznych czy SSD, a koszt losowego odczytu jest znacznie wyższy od odczytu sekwencyjnego. To jest też niezła opcja, gdy masz narzucone ograniczenia na algorytmy lub nie możesz sobie pozwolić na pełne binarne wyszukiwanie z różnych powodów technicznych. Warto też zauważyć, że jump search dobrze ilustruje ogólną ideę ograniczania przestrzeni poszukiwań bez konieczności przechodzenia przez wszystkie elementy – czyli bardzo praktyczne podejście, które daje się rozwinąć w innych algorytmach. Szczerze? Moim zdaniem, każdy, kto myśli o optymalizacji prostych operacji na dużych zbiorach danych, powinien przynajmniej raz przetestować jump search na własnych danych – efekty bywają zaskakująco dobre, zwłaszcza przy większych strukturach.