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
A. Exponential search
B. Binary search
C. Ternary search
D. Jump search
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.
Wydaje się, że wybór padł na inną metodę wyszukiwania niż jump search – spróbuję wyjaśnić, skąd mogły się wziąć takie wątpliwości. Exponential search rzeczywiście działa na posortowanych tablicach, ale jego główna idea to szybkie znajdowanie zakresu, w którym może się znajdować poszukiwany element, poprzez wykładnicze zwiększanie indeksu (czyli 1, 2, 4, 8 itd.), a dopiero później użycie binary search do finalnego wyszukiwania w wykrytym przedziale. To nie jest metoda z dzieleniem tablicy na kilka części i szukaniem liniowo po „bloku”. Ternary search z kolei jest spotykany głównie tam, gdzie szukamy ekstremum (minimum lub maksimum) funkcji unimodalnej, a nie konkretnego elementu w tablicy. Tutaj tablica jest dzielona na trzy części, ale to zupełnie inna idea niż jump search – chodzi o ciągłe zawężanie przedziału na podstawie wartości funkcji, a nie liniowe przeszukiwanie fragmentu tablicy. Binary search jest chyba najbardziej znaną metodą dla uporządkowanych tablic: dzieli zbiór na pół i eliminuje połowę elementów w każdej iteracji. Jednak tutaj nie ma podziału na „bloki” i nie wykonuje się wyszukiwania liniowego, tylko zawsze korzysta z bezpośrednich porównań środkowego elementu. Z mojego doświadczenia, najczęstszy błąd przy tego typu pytaniach to mylenie mechanizmów dzielenia tablicy i przyspieszania wyszukiwania – nie każda metoda, która coś „dzieli” albo „przeskakuje”, działa tak samo. W praktyce jump search jest czymś dość specyficznym i bardzo łatwo można go pomylić z innymi klasykami, zwłaszcza jeśli nie miało się okazji widzieć jego działania na żywo. Warto zapamiętać, że to właśnie ten algorytm łączy w sobie blokowe przeskoki i liniowe przeszukiwanie tylko wybranego fragmentu – i to go wyróżnia spośród pozostałych popularnych metod branżowych.