Porównania
Nadal możliwe
Wyszukiwanie binarne potrzebowałoby

  • Szukana wartość
  • Nadal możliwe
  • Porównywane
  • Wykluczone
  • Znalezione

Więcej o wyszukiwaniu wykładniczym

Wyszukiwanie wykładnicze

Wyszukiwanie wykładnicze znajduje wartość na posortowanej liście w dwóch fazach. Najpierw sprawdza miejsca 1, 2, 4, 8, 16 i tak dalej, za każdym razem podwajając, aż wartość w danym miejscu nie będzie mniejsza od szukanej. Potem przeszukuje binarnie odcinek między dwoma ostatnimi miejscami. Wybierz wartość do znalezienia i zobacz, dlaczego wartości blisko początku są znajdowane w zaledwie kilku porównaniach. Naciśnij Odtwórz, aby obejrzeć wyszukiwanie, albo Krok i Wstecz, aby przechodzić krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Przerywana linia oznacza szukaną wartość, a zacieniowana część to obszar, w którym może jeszcze być. Wyszukiwanie wykładnicze wymaga posortowanej listy, więc nieposortowana lista jest najpierw sortowana. Wybierz wartość, liczbę słupków albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.

Jak to działa

  1. Wybierz wartość do znalezienia i liczbę słupków. Możesz też wpisać własne liczby: wyszukiwanie wykładnicze najpierw je posortuje.
  2. Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce wyszukiwania.
  3. Wyszukaj wartość blisko początku i jedną blisko końca, i porównaj licznik z kafelkiem Wyszukiwanie binarne potrzebowałoby.

Jak działa wyszukiwanie wykładnicze

Sprawdź wartość na miejscu 1. Jeśli jest mniejsza od szukanej, sprawdź miejsce 2, potem 4, 8, 16, za każdym razem podwajając. Gdy tylko wartość nie jest mniejsza, zatrzymaj się: szukana wartość może leżeć tylko za poprzednim sprawdzonym miejscem i przed obecnym. Przeszukaj ten odcinek binarnie. Jeśli podwajanie wyjdzie poza koniec listy, szukaj binarnie od ostatniego sprawdzonego miejsca do końca.

Szybko blisko początku i bez znajomości długości

Aby dotrzeć do wartości na miejscu i, podwajanie potrzebuje około log₂ i sprawdzeń, a znaleziony odcinek ma mniej niż i wartości, więc wyszukiwanie binarne potrzebuje jeszcze około log₂ i. Razem to około 2 log₂ i, co zależy od tego, gdzie jest szukana wartość, a nie od długości listy. Wartości blisko początku są znajdowane szybciej niż zwykłym wyszukiwaniem binarnym; wartości blisko końca kosztują do około dwóch razy więcej. Ponieważ długość listy nigdy nie jest potrzebna, metoda działa też na listach zbyt długich, by je zmierzyć, albo bez znanego końca.

Często zadawane pytania

Jak działa wyszukiwanie wykładnicze?

Na posortowanej liście sprawdza miejsca 1, 2, 4, 8 i tak dalej, aż wartość w danym miejscu nie będzie mniejsza od szukanej. Wtedy szukana wartość może leżeć tylko między dwoma ostatnio sprawdzonymi miejscami, a wyszukiwanie binarne na tym odcinku ją znajduje.

Czy wyszukiwanie wykładnicze jest szybsze od binarnego?

Gdy szukana wartość jest blisko początku listy, tak: dla wartości na miejscu i potrzeba około 2 log₂ i porównań, niezależnie od długości listy. Gdy jest blisko końca, zwykłe wyszukiwanie binarne jest szybsze, nawet około dwukrotnie.

Do czego się go używa?

Do przeszukiwania list o nieznanej lub nieograniczonej długości, takich jak strumień danych czy nieskończony ciąg, oraz do scalania posortowanych serii, gdzie następne dopasowanie jest zwykle blisko. Tryb galopowania w Timsort korzysta z tego samego pomysłu podwajania.

Dlaczego nazywa się wykładnicze?

Bo sprawdzane miejsca rosną wykładniczo: 1, 2, 4, 8, 16, każde dwa razy dalej niż poprzednie. Nazywa się je też wyszukiwaniem z podwajaniem albo wyszukiwaniem galopującym.

Czy moje liczby są gdzieś wysyłane?

Nie. Wyszukiwanie działa w twojej przeglądarce, a ostatnie ustawienia zostają w lokalnej pamięci tej przeglądarki.

Chcesz wypróbować?

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

Przejdź do edytora