Co to jest Jump search?
Jump search to algorytm wyszukiwania elementu w uporządkowanej tablicy. Polega na przeskakiwaniu po tablicy o stały rozmiar bloku, a następnie wykonaniu wyszukiwania liniowego tylko w tym bloku, w którym może znajdować się szukany element.
Algorytm działa tylko poprawnie wtedy, gdy dane są posortowane.
Zasada działania
Dla tablicy o długości n wybiera się rozmiar skoku, najczęściej około √n.
Przebieg:
- sprawdzane są kolejne elementy co określony skok, np. co 3 lub 4 pozycje,
- gdy algorytm znajdzie element większy od szukanego, wiadomo, że szukana wartość może być w poprzednim bloku,
- w tym bloku wykonywane jest zwykłe wyszukiwanie liniowe.
Przykład
Tablica:
[2, 5, 8, 12, 16, 23, 38, 45, 56]
Szukamy 23, skok wynosi 3.
Algorytm sprawdza np. elementy na końcach bloków:
8, 23
Po znalezieniu bloku, w którym może być wartość, wykonuje wyszukiwanie liniowe w tym fragmencie tablicy.
Złożoność
Typowa złożoność czasowa Jump search wynosi:
O(√n)
Jest to lepsze niż wyszukiwanie liniowe O(n), ale zwykle gorsze niż wyszukiwanie binarne O(log n).
Najważniejsze cechy
- wymaga posortowanej tablicy,
- dzieli tablicę na bloki,
- przeskakuje między blokami,
- w wybranym bloku stosuje wyszukiwanie liniowe,
- angielska nazwa: Jump search.