Autor: Coenga 25.06.2024

Naukę algorytmów wyszukiwania często rozpoczynamy od dwóch popularnych wersji: wyszukiwania liniowego oraz binarnego. To proste algorytmy, które stanowią doskonałe wprowadzenie do tematu wyszukiwania.

W tym artykule pokażemy Ci na czym polega wyszukiwanie liniowe oraz binarne i omówimy przykładowe implementacje w języku Python.

Co to jest wyszukiwanie liniowe?

Wyszukiwanie liniowe to prosty sposób na znalezienie elementu w kolekcji danych. Metoda polega na przeglądaniu każdego elementu po kolei, zaczynając od początku, aż do znalezienia poszukiwanego elementu lub osiągnięcia końca kolekcji.

Wyszukiwanie liniowe krok po kroku

1. Zaczynasz od pierwszego elementu w kolekcji.
2. Sprawdzasz, czy ten element jest tym, którego szukasz
3. Jeśli TAK, kończysz wyszukiwanie i zwracasz pozycję tego elementu.
4. Jeśli NIE, przechodzisz do następnego elementu
5. Powtarzasz kroki 2-4 aż znajdziesz szukany element lub dotrzesz do końca kolekcji.

Przykładowa implementacja w języku Python

Przeanalizujmy prosty przykład, który będzie odpowiedzialny za wyszukiwanie pozycji liczby znajdującej się na liście. Spójrz na przykładowe rozwiązanie problemu:

Przeanalizujmy prosty przykład, który będzie odpowiedzialny za wyszukiwanie pozycji liczby znajdującej się na liście. Spójrz na przykładowe rozwiązanie problemu:

def search_element_position(collection, element):
for i in range(len(collection)):
    if collection[i] == element:
        return i
return None

digits = [3, 5, 1, 7, 4]
element = 7
pos = search_element_position(digits, element)

print(pos)

Kod jest dość prosty. Mamy funkcję o nazwie search_element_postion(). Przyjmuje ona dwa parametry: przeszukiwana lista oraz wartość przez nas szukana. Jeśli wartość nie zostanie odnaleziona to funkcja zwraca None.

Za pomocą pętli przechodzimy przez wszystkie indeksy na liście i sprawdzamy po kolei czy element na danym indeksie jest równy poszukiwanej przez nas wartości. Wynik z naszego przykładu to 3. Oznacza to, że poszukiwana przez nas wartość 7 znajduj się na indeksie numer 3 (indeksy oczywiście są numerowane od 0).

Wyszukiwane liniowe - plusy oraz minusy

Głowną zaletą wyszukiwania liniowego jest jego prostota - można je zaimplementować za pomocą podstawowych konstrukcji typu pętla czy instrukcja warunkowa.

Wadą jest ograniczona wydajność. Takie wyszukiwanie zmusza nas do przeszukiwania całej kolekcji od początku do końca, co przy długiej liście może zająć sporo czasu.

Co to jest wyszukiwanie binarne (połówkowe)

Wyszukianie binarne działa na zasadzie podziału kolekcji na połowę i porównania poszukiwanego elementu ze środkowym kolekcji. Jeżeli element jest mniejszy niż środkowy, przeszukiwana jest lewa połowa. Jeżeli element jest większy, poszukiwana jest prawa połowa. Proces powtarzamy do momentu, gdy podlista nie będzie miala elementów.

Dlatego właśnie takie wyszukiwanie nazywamy czasem wyszukiwaniem połówkowym

Wyszukiwanie binarne krok po kroku

1. Znajdź środkowy element listy.
2. Jeżeli środkowy element jest poszukiwanym elementem to zakończ wyszukiwanie.
3. Jeżeli poszukiwany element jest mniejszy niż środkowy, przeszukaj lewą połowę listy.
4. Jeżeli poszukiwany element jest większy niż środkowy, przeszukaj prawą połowę listy.
5. Powtarzaj kroki 1-4 aż do znalezienia elementu lub gdy podlista będzie pusta.

Przykładowa implementacja w języku Python

Jak zwykle, warto pokazać przykładową implementacje. Oto nasz kod:

def binary_search(collection, element):
low = 0
high = len(collection) - 1

while low <= high:
    mid = (low + high) // 2
    guess = collection[mid]

    if guess == element:
        return mid
    if guess > element:
        high = mid - 1
    else:
        low = mid + 1

return None

sorted_list = [1, 3, 5, 7, 9]
element = 7
result = binary_search(sorted_list, element)

print(result)

Wynik jest taki sam, jak w poprzednim przykładzie: poszukiwany element znajduje się na pozycji 3.

Algorytm wyszukiwania binarnego działa na posortowanej liście, dzieląc zakres przeszukiwania na pół w każdej iteracji. Na początku ustala dolny ( low) i górny (high) indeks listy. W pętli while, dopóki dolny indeks jest mniejszy lub równy górnemu, oblicza środkowy indek (mid) i sprawdza, czy element na tym indeksie (guess) jest równy szukanemu elementowi. Jeśli tak, zwraca indeks. Jeśli guess jest większy od szukanego elementu, ogranicza zakres przeszukiwania do lewej połowy listy, aktualizują high.W przeciwnym razie ogranicza zakres do prawej połowy, aktualizując low Jeśli element nie zostanie znaleziony, zwraca none

Wyszukiwanie binarne - plusy i minusy

Dla dużych zbiorów danych, wyszukiwanie binarne jest bardziej efektywne od wyszukiwania liniowego. Wymaga jednak aby dane były wcześniej posortowane. Dla bardzo małych zbiorów danych, wyszukiwanie liniowe może być szybsze.