Wyszukiwanie wykładnicze

Wyszukiwanie binarne musi wiedzieć, gdzie kończy się lista, zanim zajrzy do środka. Wyszukiwanie wykładnicze nie musi: galopuje do przodu coraz większymi krokami, aż przeskoczy szukaną wartość, a potem przeszukuje binarnie ostatni krok. Dzięki temu świetnie nadaje się do list o nieznanej długości i jest szybkie dla wartości blisko początku.

Posortowany rząd słupków ze skokami o podwajanej długości przez miejsca 1, 2, 4 i 8 oraz zacieniowanym odcinkiem między dwoma ostatnimi skokami
Posortowany rząd słupków ze skokami o podwajanej długości przez miejsca 1, 2, 4 i 8 oraz zacieniowanym odcinkiem między dwoma ostatnimi skokami

Idea

Sprawdź wartość na miejscu 1, potem 2, 4, 8, 16 i tak dalej, każde miejsce dwa razy dalej niż poprzednie. Dopóki wartość w danym miejscu jest mniejsza od szukanej, szukana wartość musi być dalej. Gdy po raz pierwszy wartość nie jest mniejsza, szukana wartość jest w pułapce: leży za poprzednim sprawdzonym miejscem i nie dalej niż obecne. Ten odcinek jest posortowany, więc wyszukiwanie binarne znajduje szukaną wartość albo pokazuje, że jej brak.

Przykład

Szukaj 23 w 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Na miejscu 1 jest 2, na miejscu 2 jest 5, na miejscu 4 jest 12, wszystkie mniejsze. Na miejscu 8 jest 56, czyli więcej, więc 23 może być tylko na miejscach od 5 do 7. Wyszukiwanie binarne sprawdza ich środek, miejsce 6, i znajduje 23: 5 porównań, podczas gdy zwykłe wyszukiwanie binarne potrzebuje 3. Szukanie 12 na tej samej liście kończy się na miejscu 4 po 3 porównaniach, o jedno mniej niż wyszukiwanie binarne, a 2 zostaje znalezione na miejscu 1 jednym porównaniem.

Ile porównań

Dla wartości na miejscu i podwajanie kończy się po około log₂ i krokach i zostawia odcinek krótszy niż i miejsc, który wyszukiwanie binarne pokrywa w około log₂ i kolejnych. Całe wyszukiwanie kosztuje więc około 2 log₂ i porównań, niezależnie od długości listy. Gdy szukana wartość jest blisko początku, to lepiej niż wyszukiwanie binarne, które zawsze płaci około log₂ n. Gdy jest blisko końca, wyszukiwanie wykładnicze płaci do około dwóch razy więcej. Dla 40 wartości aplikacja daje średnio około 3 porównań dla pierwszych pięciu miejsc i około 9 dla ostatnich pięciu, wobec około 4,6 dla wyszukiwania binarnego.

Nieznana długość i galopowanie

Jon Bentley i Andrew Yao opisali tę strategię podwajania w 1976 roku dla wyszukiwania nieograniczonego: znajdowania wartości w posortowanym ciągu bez znanego końca, takim jak nieskończona lista albo strumień danych, który można tylko odpytywać miejsce po miejscu. Ten sam pomysł przyspiesza scalanie. Gdy jedna z dwóch posortowanych serii ciągle wygrywa, Timsort przełącza się na galopowanie: zagląda 1, 2, 4, 8 miejsc do przodu w drugiej serii, by znaleźć miejsce dla następnej wartości, zamiast przesuwać się o jedno miejsce naraz.

Wypróbuj

Otwórz aplikację, wybierz wartość w polu Szukaj i naciśnij Krok. Każde sprawdzenie miejsca 1, 2, 4, 8 i tak dalej jest podświetlane; gdy tylko wartość nie jest mniejsza, odcinek między dwoma ostatnimi miejscami zostaje zacieniowany i dalej działa wyszukiwanie binarne. Wyszukaj małą wartość, a potem dużą, i porównaj licznik z kafelkiem wyszukiwania binarnego.

Często zadawane pytania

Jaka jest złożoność czasowa wyszukiwania wykładniczego?

O(log i) dla wartości na miejscu i, czyli najwyżej O(log n) dla listy n wartości. Wymaga O(1) dodatkowej pamięci i posortowanej listy.

Czym różni się wyszukiwanie wykładnicze od binarnego?

Wyszukiwanie binarne zaczyna od całej listy i potrzebuje jej długości. Wyszukiwanie wykładnicze najpierw przez podwajanie znajduje odcinek zawierający szukaną wartość, a potem przeszukuje binarnie tylko ten odcinek. Jest szybsze, gdy szukana wartość jest blisko początku, i działa bez znajomości długości.

Dlaczego podwajać krok, a nie dodawać stałej wartości?

Dodawanie stałego kroku to wyszukiwanie skokowe (jump search), które potrzebuje około n podzielone przez krok sprawdzeń, by przejść przez listę. Podwajanie dociera do miejsca i w około log₂ i sprawdzeniach, a pozostawiony odcinek nigdy nie jest więcej niż dwa razy za duży, więc późniejsze wyszukiwanie binarne pozostaje krótkie.

Gdzie stosuje się wyszukiwanie wykładnicze?

Przy przeszukiwaniu nieograniczonych lub bardzo długich posortowanych danych, przy scalaniu posortowanych serii (galopowanie w Timsort) i przy znajdowaniu pierwszego miejsca, w którym warunek staje się prawdziwy, gdy nie znamy górnej granicy.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj wyszukiwanie wykładnicze