Wpis będzie bardzo krótki, ponieważ algorytm wyszukiwania liniowego nie należy do zbyt skomplikowanych. Jego celem jest odnalezienie konkretnej wartość w kolekcji. Argument podany podczas wywołania funkcji (opartej zwykle na typach generycznych) będzie porównywany kolejno z każdym obiektem w kolekcji do momentu wyczerpania puli lub odnalezienia szukanej wartości. Jako wynik zwracany jest numer indeksu w kolekcji lub wartość null / nil w przypadku, gdy wartość nie zostanie odnaleziona.

Wyszukiwanie liniowe nie jest specjalnie wydajnym algorytmem (o czym będzie na końcu) i lepszą alternatywą w większości przypadków jest wyszukiwanie binarne. Pomimo tego wyszukiwanie liniowe stanowi bardzo dobre wprowadzenie w świat algorytmów.

Z racji tego, że od jakiegoś czasu grzebię trochę w Kotlinie, od tego wpisu przykłady algorytmów prezentować będę także w tym języku (obok Swifta). Do testowania kodu mam utworzony osobnym projekt w Android Studio, w którym umieszczam wszystkie swoje przykłady. Jeżeli chodzi o Swift’a, to najlepiej skorzystać z Playground.

Tak prezentuje się implementacja w poszczególnych językach:

Kotlin:

 

Swift:

Sprawdźmy algorytm w praktyce. Załóżmy, że mamy kolekcję składającą się z obiektów typu String:

Chcemy sprawdzić, czy w kolekcji znajduje się imię „Darek”. Teraz widać gołym okiem, że nie znajdziemy dopasowania, ale wyobraźcie sobie, że nie macie podglądu i nie możecie sprawdzić co dokładnie i na jakiej pozycji znajduje się w kolekcji 🤓:

Kotlin:

 

Swift:

W naszej kolekcji nie znajdziemy „Darka”, więc funkcja zwróci nam null / nil.

Sprawdźmy jednak jaki będzie wynik jeżeli będziemy chcieli odnaleźć imię „Erwin”:

Kotlin:

 

Swift:

Tym razem udało się odnaleźć pasujący element i funkcja zwróciła nam wartość 3, czyli numer indeksu pod którym ukrywa się poszukiwany obiekt 🧐.

 

Wydajność

 

Na samy początku wspomniałem, że wyszukiwanie liniowe nie stanowi najbardziej optymalnego rozwiązania. A to dlatego, że w najgorszym wypadku musimy przeszukać całą kolekcję, aby odnaleźć właściwy obiekt lub dowiedzieć się, że w kolekcji go nie ma. Oczywiście może zdarzyć się tak, że poszukiwany obiekt będzie znajdował się na samy początku kolekcji, ale na to bym za bardzo nie liczył 😅.

Z powyższego wynika, że w najgorszym wypadku koszt wyszukiwana liniowego wynosi O(n), co oznacza, że będzie się on zwiększał proporcjonalnie do wzrostu liczby elementów w kolekcji. W najlepszym wypadku koszt będzie wynosił O(1), czyli będzie stały.

 

Słowo na drogę

 

I to by było na tyle. W następnym wpisie skupię się na algorytmie Rabin-Karp, który pozwala na przeszukiwanie obiektów typu String w poszukiwaniu określonego wzorca. Do następnego 😎.

 

Link do obrazka tytułowego

 

 


 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *