Wyszukiwanie liniowe a binarne
Wyszukiwanie liniowe a binarne to interaktywny eksperyment z aplikacji Algorytmy w akcji – darmowej symulacji ze StudyFi Lab, która działa bezpośrednio w przeglądarce.
Wyszukiwanie liniowe sprawdza elementy po kolei, więc w najgorszym przypadku potrzebuje n kroków — O(n). Wyszukiwanie binarne działa tylko na posortowanej tablicy: patrzy na środek i zależnie od wyniku odrzuca całą połowę. Po każdym kroku zostaje najwyżej połowa, dlatego wystarczy najwyżej ⌈log₂(n+1)⌉ kroków — O(log n). Dla 40 elementów to 6 kroków zamiast 40.
Spróbuj: Ustaw 40 elementów i szukaj ostatniej wartości. Potem wybierz liczbę, której nie ma w tablicy — ile kroków potrzebuje każde wyszukiwanie, żeby to stwierdzić?
Najczęstsze pytania
Co pokazuje eksperyment „Wyszukiwanie liniowe a binarne”?
Wyszukiwanie liniowe sprawdza elementy po kolei, więc w najgorszym przypadku potrzebuje n kroków — O(n). Wyszukiwanie binarne działa tylko na posortowanej tablicy: patrzy na środek i zależnie od wyniku odrzuca całą połowę. Po każdym kroku zostaje najwyżej połowa, dlatego wystarczy najwyżej ⌈log₂(n+1)⌉ kroków — O(log n). Dla 40 elementów to 6 kroków zamiast 40.
Jak wypróbować „Wyszukiwanie liniowe a binarne”?
Ustaw 40 elementów i szukaj ostatniej wartości. Potem wybierz liczbę, której nie ma w tablicy — ile kroków potrzebuje każde wyszukiwanie, żeby to stwierdzić?
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.