- Szukana wartość
- Nadal możliwe
- Porównywane
- Wykluczone
- Znalezione
Wyszukiwanie binarne
Wyszukiwanie binarne znajduje wartość na posortowanej liście, zaglądając zawsze do środka. Jeśli środkowa wartość jest za mała, szukana może być tylko za nią; jeśli za duża, tylko przed nią. Tak czy inaczej połowa tego, co zostało, odpada. Wybierz wartość do wyszukania, przechodź przez wyszukiwanie krok po kroku i patrz, jak zacieniony obszar się kurczy, aż wartość zostanie znaleziona albo nic nie zostanie. 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. Przerywana linia oznacza szukaną wartość, a zacieniony obszar to miejsce, gdzie może się jeszcze znajdować. Wyszukiwanie binarne 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
- Wybierz wartość do wyszukania i liczbę słupków. Możesz też wpisać własne liczby: wyszukiwanie binarne 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.
- Porównaj kafelek Porównania z kafelkiem Wyszukiwanie liniowe potrzebowałoby dla wartości blisko końca albo takiej, której brakuje.
Jak działa wyszukiwanie binarne
Śledź tę część posortowanej listy, w której szukana wartość może się jeszcze znajdować; na początku to cała lista. Spójrz na wartość w jej środku. Jeśli jest równa szukanej, gotowe. Jeśli jest mniejsza, szukana może być tylko za nią, więc kontynuuj z częścią za środkiem. Jeśli jest większa, kontynuuj z częścią przed nim. Gdy nic nie zostanie, szukanej wartości nie ma na liście.
Dlaczego jest tak szybkie
Każde porównanie zmniejsza o połowę część, która została. Z n wartości po k porównaniach zostaje najwyżej około n/2ᵏ, więc wyszukiwanie kończy się po najwyżej ⌊log₂ n⌋ + 1 porównaniach: 6 dla 40 wartości, 10 dla 1000, 20 dla miliona. Wyszukiwanie liniowe może musieć sprawdzić każdą wartość. Haczyk w tym, że lista musi być posortowana, a utrzymywanie jej w porządku albo sortowanie na początku też kosztuje.
Często zadawane pytania
Jak działa wyszukiwanie binarne?
Porównuje szukaną wartość ze środkową wartością tej części posortowanej listy, w której może się ona jeszcze znajdować. Równe oznacza znalezione; w przeciwnym razie odpada połowa, w której szukanej wartości być nie może, a wyszukiwanie trwa w drugiej połowie, aż wartość zostanie znaleziona albo nic nie zostanie.
Ile porównań potrzebuje wyszukiwanie binarne?
Najwyżej ⌊log₂ n⌋ + 1 dla listy n wartości: 6 dla 40, 10 dla 1000, 20 dla miliona. Każde porównanie zmniejsza o połowę to, co zostało.
Dlaczego wyszukiwanie binarne wymaga posortowanej listy?
Bo tylko na posortowanej liście jedno porównanie mówi, po której stronie jest szukana wartość. Na nieposortowanej liście mniejsza wartość w środku nic nie mówi o tym, gdzie jest szukana, więc niczego nie da się wykluczyć.
Którą wartość znajduje, gdy są duplikaty?
Dowolną z nich, zależnie od tego, gdzie wypadają środki. Warianty, które po trafieniu szukają dalej w lewo lub w prawo, znajdują pierwsze albo ostatnie wystąpienie.
Czy moje liczby są gdzieś wysyłane?
Nie. Wyszukiwanie działa w twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej 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