- Szukana wartość
- Porównywane
- Wykluczone
- Znalezione
Wyszukiwanie liniowe
Wyszukiwanie liniowe to najprostszy sposób na znalezienie wartości: zacznij od początku i sprawdzaj każdą wartość po kolei, aż się znajdzie. Działa na każdej liście, posortowanej lub nie. Wybierz szukaną wartość, odtwórz wyszukiwanie albo przechodź przez nie po jednym porównaniu i zobacz, jak koszt zależy od tego, gdzie jest wartość i czy w ogóle jest na liście. Naciśnij Odtwórz, aby obejrzeć wyszukiwanie, albo Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Linia przerywana oznacza szukaną wartość. Wybierz wartość, liczbę słupków, ich początkowy układ albo wpisz własne liczby. Wyłącz Zatrzymaj przy pierwszym trafieniu, aby znaleźć wszystkie trafienia. 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, liczbę słupków i ich początkowy układ. Możesz też wpisać własne liczby.
- Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce wyszukiwania.
- Wyłącz Zatrzymaj przy pierwszym trafieniu, aby sprawdzić każdą wartość i znaleźć wszystkie trafienia.
Jak działa wyszukiwanie liniowe
Porównaj pierwszą wartość z szukaną. Jeśli są równe, gotowe. Jeśli nie, przejdź do drugiej wartości, potem do trzeciej i tak dalej. Jeśli dojdziesz do końca listy bez trafienia, szukanej wartości nie ma na liście. Nie trzeba niczego przygotowywać: lista nie musi być posortowana.
Ile porównań
Wartość na pozycji k zostaje znaleziona po k porównaniach. Najlepszy przypadek to jedno porównanie, gdy szukana wartość jest pierwsza. Najgorszy to n, gdy jest ostatnia albo jej brak, bo dopiero po sprawdzeniu każdej wartości możesz mieć pewność, że jej nie ma. Średnio dla wartości, która jest na liście, potrzeba około (n + 1)/2. Dla posortowanej listy wyszukiwanie binarne radzi sobie dużo lepiej: około log₂ n porównań, 6 zamiast nawet 40 przy 40 wartościach.
Często zadawane pytania
Jak działa wyszukiwanie liniowe?
Sprawdza wartości listy po kolei, od pierwszej do ostatniej, aż znajdzie szukaną wartość albo skończą się wartości. Nazywa się je też wyszukiwaniem sekwencyjnym.
Jaka jest złożoność czasowa wyszukiwania liniowego?
O(n): w najgorszym przypadku, gdy szukana wartość jest ostatnia albo jej brak, porównuje ją ze wszystkimi n wartościami. Średnio dla wartości, która jest na liście, potrzeba około (n + 1)/2 porównań.
Kiedy wyszukiwanie liniowe to dobry wybór?
Przy krótkich listach, przy listach nieposortowanych, które przeszukuje się tylko raz czy dwa, i przy danych, które można czytać tylko po kolei, na przykład strumieniu. Wcześniejsze sortowanie, aby użyć wyszukiwania binarnego, opłaca się tylko wtedy, gdy szukasz wiele razy.
Dlaczego brakująca wartość kosztuje najwięcej?
Bo nic nie daje wyszukiwaniu liniowemu sygnału, by przerwać wcześniej. Trafienie można wykluczyć tylko, sprawdzając każdą wartość, więc wartość, której nie ma na liście, zawsze wymaga n porównań.
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