- Szukana wartość
- Nadal możliwe
- Porównywane
- Wykluczone
- Znalezione
Wyszukiwanie interpolacyjne
Wyszukiwanie interpolacyjne szuka wartości w posortowanej liście tak, jak otwierasz książkę telefoniczną: nazwiska na T szukasz blisko końca, a nie w środku. Szacuje miejsce szukanej wartości na podstawie wartości na obu końcach pozostałej części. Wybierz wartość i rozkład wartości, przejdź krok po kroku przez kolejne próby i zobacz, kiedy oszacowanie wygrywa z wyszukiwaniem binarnym, a kiedy nie. Naciśnij Odtwórz, aby obejrzeć wyszukiwanie, albo Krok i Wstecz, aby przechodzić po jednym kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Linia przerywana oznacza szukaną wartość, a zacieniona część to miejsce, gdzie wciąż może być. Wyszukiwanie interpolacyjne wymaga posortowanej listy, więc nieposortowana lista jest najpierw sortowana. Wybierz wartość, rozkład wartości, 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
- Wybierz wartość do wyszukania, rozkład wartości i liczbę słupków. Możesz też wpisać własne liczby: wyszukiwanie interpolacyjne najpierw je posortuje.
- Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednym kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce wyszukiwania.
- Przełączaj Rozkład między opcjami Równomierny, Losowe luki i Skośny, i porównuj Próby z polem Wyszukiwanie binarne potrzebowałoby.
Jak działa wyszukiwanie interpolacyjne
Spójrz na pierwszą i ostatnią wartość tej części posortowanej listy, w której wciąż może być szukana wartość. Jeśli leży ona, powiedzmy, w 40% drogi od pierwszej wartości do ostatniej, sprawdź miejsce w 40% drogi wzdłuż listy. Jeśli jest tam szukana wartość, gotowe. Jeśli jest tam mniejsza, zostają tylko dalsze miejsca; jeśli większa, tylko wcześniejsze. Oszacuj ponownie w tym, co zostało. Jeśli szukana wartość jest mniejsza od pierwszej wartości lub większa od ostatniej, nie ma jej na liście.
Kiedy oszacowanie działa
Jeśli wartości są rozłożone równomiernie, jak 10, 20, 30 i tak dalej, pierwsze oszacowanie trafia w szukaną wartość albo bardzo blisko niej, a wyszukiwanie potrzebuje średnio około log₂(log₂ n) prób: około 5 dla miliarda wartości, wobec 30 przy wyszukiwaniu binarnym. Jeśli wartości się skupiają, jak 1, 2, 3, 4, 1000, oszacowania ciągle trafiają w złe miejsce i każda próba może usunąć tylko jedną wartość, więc w najgorszym przypadku potrzeba n prób. Wyszukiwanie binarne nigdy nie wypada gorzej niż około log₂ n.
Często zadawane pytania
Jak działa wyszukiwanie interpolacyjne?
W posortowanej liście szacuje, gdzie powinna być szukana wartość, na podstawie pierwszej i ostatniej wartości pozostałej części, sprawdza to miejsce i zostawia tylko część po właściwej stronie. To jak wyszukiwanie binarne ze sprytniejszym zgadywaniem niż środek.
Czy wyszukiwanie interpolacyjne jest szybsze od binarnego?
Przy równomiernie rozłożonych wartościach tak: średnio około log₂(log₂ n) prób zamiast około log₂ n. Przy nierównomiernie rozłożonych wartościach może być dużo wolniejsze, nawet n prób, podczas gdy wyszukiwanie binarne nigdy nie potrzebuje więcej niż około log₂ n.
Dlaczego może być wolne?
Bo oszacowanie zakłada, że wartości rosną równomiernie. Jeśli większość wartości jest mała, a kilka ogromnych, oszacowanie dla małej szukanej wartości raz po raz trafia blisko początku i za każdym razem usuwa tylko jedną lub dwie wartości.
Gdzie stosuje się wyszukiwanie interpolacyjne?
Tam, gdzie klucze są rozłożone prawie równomiernie, a próby są kosztowne, na przykład przy wyszukiwaniu rekordów na dysku po numerycznym ID lub haszu. Wiele systemów łączy je z wyszukiwaniem binarnym, aby zachować dobry najgorszy przypadek.
Czy moje liczby są gdzieś wysyłane?
Nie. Wyszukiwanie działa w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora