Podcast o Wyszukiwanie liniowe i binarne

Kapitoly

Metoda na skarpetkę

Jak to działa?

Przykład i złożoność

Wady i zalety

Wyszukiwanie Binarne

Přepis

Lena: ...i serio, to jest jak szukanie jednej konkretnej skarpety w wielkiej szufladzie nieposortowanych ubrań!

Michał: Dokładnie! Po prostu bierzesz jedną rzecz po drugiej, aż w końcu ją znajdziesz. To takie proste i intuicyjne.

Lena: I to jest cała magia, naprawdę. Żadnych skomplikowanych warunków na start.

Michał: Cześć wszystkim, słuchacie Studyfi Podcast. Ja jestem Michał...

Lena: ...a ja Lena. I dzisiaj rozkładamy na czynniki pierwsze wyszukiwanie liniowe. Inaczej zwane sekwencyjnym.

Michał: Dobrze, to trzymajmy się tej szuflady ze skarpetkami. Jak to wygląda krok po kroku w języku informatyki?

Lena: Świetne pytanie! Wyobraź sobie, że masz listę liczb. Algorytm startuje od pierwszej, porównuje ją z tą, której szukasz. Pasuje?

Michał: Załóżmy, że nie. Co dalej?

Lena: To idzie do następnej liczby. I znowu porównuje. Robi to tak długo, aż znajdzie to, czego szuka, albo dojdzie do końca listy.

Michał: Czyli kluczowe jest to, że dane nie muszą być w żaden sposób posortowane? Mogą być w totalnym bałaganie?

Lena: Dokładnie! I to jest największa zaleta tej metody. Prostota i brak wymagań wstępnych.

Michał: Okej, to może jakiś konkretny przykład? Powiedzmy, że mamy tablicę: i szukamy liczby 42.

Lena: Dobra. Algorytm sprawdzi: 15? Nie. 8? Też nie. 23... 4... Aż w końcu trafi na 42 na piątej pozycji i powie: „Mam cię!”.

Michał: A co, jeśli szukalibyśmy liczby 99, której tam nie ma?

Lena: Wtedy algorytm musi być bardzo cierpliwy. Sprawdziłby wszystkie sześć liczb, doszedłby do końca i dopiero wtedy stwierdziłby: „Niestety, brak”.

Michał: Rozumiem. To oznacza, że w najgorszym wypadku musimy przejrzeć całą listę. Jak to się nazywa w informatyce?

Lena: To jest tak zwana złożoność obliczeniowa, a dla wyszukiwania liniowego wynosi ona **O(n)**. Oznacza to, że czas wyszukiwania rośnie proporcjonalnie do liczby elementów. Dwa razy więcej danych, mniej więcej dwa razy dłuższy czas oczekiwania.

Michał: Czyli podsumowując: zaletą jest prostota i to, że działa na nieposortowanych danych.

Lena: Tak. Jest super łatwe do zaimplementowania. Ale ma jedną, zasadniczą wadę.

Michał: Jest po prostu wolne przy dużych zbiorach danych, zgadza się?

Lena: W punkt. Jeśli masz milion elementów, w najgorszym razie musisz wykonać milion porównań. To dlatego do większych zadań potrzebujemy czegoś sprytniejszego.

Michał: Okej, więc wyszukiwanie liniowe jest proste, ale brzmi... no, wolno. Jest jakiś szybszy sposób?

Lena: Oczywiście! I to prowadzi nas do naszego ostatniego tematu na dziś: wyszukiwania binarnego.

Michał: Wyszukiwanie binarne... brzmi o wiele bardziej zaawansowanie.

Lena: Jest niesamowicie wydajne, ale ma jedną kluczową zasadę. Dane *muszą* być posortowane. To warunek konieczny.

Michał: Dobra, więc mamy posortowaną listę. Jak to w ogóle działa?

Lena: Pomyśl o tym jak o zgadywaniu liczby od 1 do 100. Przecież nie zgadujesz po kolei: 1, 2, 3... prawda?

Michał: No nie, zacząłbym od środka, na przykład 50.

Lena: Dokładnie! Wyszukiwanie binarne robi to samo. Sprawdza środkowy element listy.

Michał: A jeśli to nie jest szukana wartość?

Lena: Algorytm ustala, czy szukany element jest mniejszy, czy większy. Na tej podstawie odrzuca całą połowę listy i powtarza proces dla tej drugiej połówki.

Michał: Czyli za każdym razem zmniejsza problem o połowę. To genialne! Trochę jak szukanie słowa w słowniku.

Lena: Właśnie! Nie zaczynasz od pierwszej strony. Otwierasz gdzieś pośrodku i sprawdzasz.

Michał: Wow, co za świetne podsumowanie. Czyli reasumując: mamy proste wyszukiwanie liniowe i znacznie szybsze, binarne, które działa na zasadzie „dziel i zwyciężaj” dla posortowanych danych.

Lena: Zgadza się! Mam nadzieję, że to pomoże wszystkim w nauce. To była przyjemność, Michał.

Michał: Dla mnie również, Lena! Dziękujemy za wysłuchanie Studyfi Podcast. Do usłyszenia!