Wyszukiwanie skokowe
Wyszukiwanie skokowe przypomina szukanie strony w książce bez spisu treści: przewracasz po kilka kartek naraz, zerkając na numery stron, a gdy zajdziesz za daleko, cofasz się przez ostatni fragment. Na posortowanej liście wymaga znacznie mniej porównań niż sprawdzanie każdej wartości.
Idea
W posortowanej liście ostatnia wartość bloku mówi, czy szukana wartość w ogóle może być w tym bloku: jeśli jest mniejsza od szukanej, każda wartość w bloku też jest mniejsza. Nie trzeba więc zaglądać do środka. Sprawdzaj po kolei ostatnią wartość każdego bloku, pomijając całe bloki, aż któraś nie będzie mniejsza od szukanej. Wtedy szukana wartość może być tylko w tym bloku: przeszukaj go od początku.
Przykład
Szukaj 23 w liście 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, w blokach po 3. Pierwszy blok kończy się na 8, które jest mniejsze, więc go pomiń. Drugi blok kończy się na 23, które nie jest mniejsze, więc 23 może być tylko wśród 12, 16, 23. Przeszukanie daje 12, 16, a potem 23: znalezione po 5 porównaniach, podczas gdy wyszukiwanie liniowe potrzebuje 6, a binarne 3. Przy szukaniu 40 końce bloków 8, 23 i 72 prowadzą do bloku 38, 56, 72; 38 jest mniejsze, a 56 już większe, więc 40 tam nie ma: znowu 5 porównań.
Dlaczego √n
Przy blokach po m wartości znalezienie właściwego bloku zajmuje najwyżej około n/m porównań, a przeszukanie go najwyżej m. Nieliczne, długie skoki wydłużają przeszukiwanie; liczne, krótkie skoki wydłużają skakanie. Suma n/m + m jest najmniejsza, gdy obie części są równe, czyli dla m = √n, i wynosi wtedy około 2√n. Dla 40 wartości oznacza to bloki po 6 i najwyżej 13 porównań; dla miliona wartości bloki po 1000 i około 2000 porównań.
Gdzie się sprawdza
Wyszukiwanie binarne potrzebuje mniej porównań, około log₂ n. Ale skacze tam i z powrotem po całej liście, a wyszukiwanie skokowe idzie tylko do przodu i cofa się raz, na początek jednego bloku. Dlatego było atrakcyjne dla danych na taśmie lub w strukturze z dowiązaniami, gdzie cofanie się jest wolne. Ben Shneiderman opisał je w 1978 roku jako jump searching. Ten sam pomysł podziału na √n bloków, często nazywany dekompozycją pierwiastkową, pojawia się w wielu innych algorytmach.
Wypróbuj
Otwórz aplikację, wybierz wartość w polu Szukaj i naciśnij Krok. Każdy skok wyróżnia ostatnią wartość bloku; pominięte bloki blakną, a blok, w którym może być szukana wartość, jest zacieniony podczas przeszukiwania. Zmień Długość skoku z √n na 2 lub 8 przy 40 słupkach i zobacz, jak przesuwa się równowaga między skokami a przeszukiwaniem.
Często zadawane pytania
Jaka jest złożoność czasowa wyszukiwania skokowego?
O(√n) przy blokach po √n wartości: najwyżej około 2√n porównań. Potrzebuje O(1) dodatkowej pamięci i posortowanej listy.
Czym różni się wyszukiwanie skokowe od binarnego?
Wyszukiwanie binarne za każdym razem dzieli pozostałą część na pół i potrzebuje około log₂ n porównań, ale chodzi tam i z powrotem. Wyszukiwanie skokowe przeskakuje do przodu o stałe kroki i przeszukuje jeden blok, potrzebuje około 2√n porównań i cofa się tylko raz.
Czy ostatni blok można zamiast tego przeszukać binarnie?
Tak. Wyszukiwanie binarne w bloku zmniejsza przeszukiwanie z m porównań do około log₂ m. Skoki nadal kosztują n/m, więc wtedy opłacają się większe bloki.
Czy wyszukiwanie skokowe wymaga posortowanej listy?
Tak. Pominięcie bloku jest bezpieczne tylko dlatego, że mniejsza ostatnia wartość oznacza, że każda wartość w bloku jest mniejsza. Aplikacja najpierw sortuje nieposortowaną listę.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj wyszukiwanie skokowe