Implementacje algorytmów wyszukiwania w języku Python

Implementacja funkcji wyszukującej stanowi zawsze pewne wyzwanie, jednakże nie jest to zadanie nieosiągalne.

W codziennych sytuacjach poszukiwania odbywają się w sposób niesystematyczny. Zazwyczaj udajemy się do miejsc, które wydają nam się najbardziej prawdopodobne do znalezienia poszukiwanego przedmiotu. Rzadko kiedy działamy według ściśle określonego planu.

Czy ten sam sposób postępowania ma zastosowanie w świecie programowania?

Odpowiedź brzmi: nie! W programowaniu musi istnieć pewien schemat działania, umożliwiający efektywne przeszukiwanie danych. W niniejszym artykule przyjrzymy się kilku algorytmom, które wykorzystują różnorodne strategie wyszukiwania.

W obszarze programowania istnieje wiele algorytmów wyszukiwania. W tym tekście skupimy się na tych najważniejszych i najczęściej używanych. Opanowanie ich pozwoli na łatwiejsze zrozumienie pozostałych algorytmów.

W tym artykule, termin „wyszukiwanie” będzie odnosił się do poszukiwania konkretnego elementu w tablicy danych.

Przejdźmy teraz do omówienia poszczególnych algorytmów.

Wyszukiwanie Liniowe

Nazwa tego algorytmu sugeruje, że wyszukiwanie elementów w tablicy odbywa się w sposób liniowy. Algorytm rozpoczyna poszukiwania od początku tablicy i przesuwa się kolejno, aż do znalezienia poszukiwanego elementu lub do końca tablicy. Po znalezieniu elementu, działanie programu zostaje zatrzymane.

Aby lepiej zrozumieć działanie algorytmu wyszukiwania liniowego, posłużymy się kilkoma ilustracjami.

Analizując proces wyszukiwania, można zauważyć, że w najgorszym przypadku czas wykonania algorytmu wynosi O(n). Podczas analizy algorytmów, zawsze należy brać pod uwagę złożoność czasową w najmniej korzystnym scenariuszu. Zatem, złożoność czasowa algorytmu liniowego wynosi O(n).

Przejdźmy do implementacji algorytmu wyszukiwania liniowego.

Implementacja Wyszukiwania Liniowego

Teraz, gdy już rozumiesz działanie algorytmu wyszukiwania liniowego, spróbujmy przenieść teorię na praktykę. Najpierw omówimy sposób implementacji wyszukiwania liniowego, a następnie spróbujesz samodzielnie go zakodować. Nie obawiaj się, jeśli napotkasz trudności, kod zostanie przedstawiony w dalszej części artykułu.

Zatem, zobaczmy jak zaimplementować algorytm wyszukiwania liniowego:

• Zdefiniuj tablicę elementów (Twoje ulubione liczby).
• Stwórz funkcję o nazwie `szukaj_elementu`, która będzie przyjmować trzy argumenty: tablicę, jej długość oraz poszukiwany element.
• `szukaj_elementu(tablica, n, element)`:
  • Przejdź iteracyjnie przez tablicę.
    • Sprawdź, czy aktualnie analizowany element jest identyczny z poszukiwanym elementem.
    • Jeśli tak, zwróć wartość True.
  • Po zakończeniu iteracji, jeśli funkcja nadal działa, oznacza to, że element nie występuje w tablicy. W takim przypadku zwróć wartość False.
• Wyświetl odpowiedni komunikat na podstawie wartości zwróconej przez funkcję `szukaj_elementu`.

Wykorzystując powyższe kroki, spróbuj samodzielnie zaimplementować algorytm wyszukiwania liniowego.

Udało Ci się zakończyć implementację? Mam nadzieję, że tak! Jeśli zakończyłeś, porównaj swój kod z poniższym.

Jeżeli nie udało Ci się, nie przejmuj się. Przeanalizuj poniższy kod i spróbuj zrozumieć sposób jego działania. Z pewnością szybko dojdziesz do wprawy.

## funkcja wyszukiwania
def szukaj_elementu(arr, n, element):

	## iteracja po tablicy
	for i in range(n):

		## porównanie aktualnego elementu z poszukiwanym
		if arr[i] == element:
			## zwrot wartości True, jeśli element zostanie znaleziony
			return True

	## element nie został znaleziony, dlatego funkcja dochodzi do tego miejsca
	return False


if __name__ == '__main__':
	## inicjalizacja tablicy, jej długości i szukanego elementu
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_do_znalezienia = 6
	# element_do_znalezienia = 11

	if szukaj_elementu(arr, n, element_do_znalezienia):
		print(element_do_znalezienia, "został znaleziony")
	else:
		print(element_do_znalezienia, "nie został znaleziony")

Uruchom program najpierw z elementem, który znajduje się w tablicy, a następnie z takim, którego w niej nie ma.

Złożoność czasowa algorytmu wyszukiwania liniowego wynosi O(n).

Czy możemy ją jeszcze bardziej zmniejszyć, wykorzystując inne metody?

Odpowiedź brzmi: tak. Przekonajmy się jak.

Wyszukiwanie Binarne

Algorytm wyszukiwania binarnego polega na ciągłym sprawdzaniu środkowego elementu tablicy. Algorytm ten jest wykorzystywany do wyszukiwania elementów w tablicach, które są posortowane.

Algorytm wyszukiwania binarnego iteruje po tablicy, sprawdzając środkowy element. Jeśli poszukiwany element zostanie znaleziony, program kończy swoje działanie. W przeciwnym wypadku, jeśli środkowy element jest mniejszy niż element poszukiwany, algorytm pomija lewą część tablicy (wraz ze środkowym elementem). Jeśli natomiast środkowy element jest większy od poszukiwanego, algorytm pomija prawą część tablicy (również ze środkowym elementem).

W każdym kroku iteracji algorytm wyszukiwania binarnego zmniejsza zakres poszukiwania. Zatem, liczba porównań jest mniejsza niż w przypadku algorytmu wyszukiwania liniowego.

Ilustracje pomogą nam w lepszym zrozumieniu algorytmu wyszukiwania binarnego. Przyjrzyjmy się im.

Złożoność czasowa algorytmu wyszukiwania binarnego wynosi O(log n). W każdej iteracji zakres poszukiwań zmniejsza się o połowę, co skutkuje wykładniczym zmniejszeniem liczby kroków.

Implementacja Wyszukiwania Binarnego

Najpierw omówimy kroki implementacji algorytmu wyszukiwania binarnego, a następnie przejdziemy do kodu. Zobaczmy, jak zrealizować implementację.

• Zdefiniuj tablicę zawierającą elementy (Twoje szczęśliwe liczby).
• Napisz funkcję o nazwie `szukaj_elementu`, która przyjmuje trzy parametry: posortowaną tablicę, jej długość oraz poszukiwany element.
• `szukaj_elementu(posortowana_arr, n, element)`:
  • Zainicjuj zmienną `i` jako indeks do iteracji po tablicy.
  • Następnie zainicjuj dwie zmienne, które będą przechowywać początkowy i końcowy indeks zakresu wyszukiwania. Nazwijmy je `początek` i `koniec`.
  • Iteruj tak długo, jak długo `i` jest mniejsze od długości tablicy.
    • Oblicz środkowy indeks zakresu wyszukiwania, korzystając z wartości `początek` i `koniec`. Będzie on równy `(początek + koniec) // 2`.
    • Sprawdź, czy element o środkowym indeksie jest równy elementowi poszukiwanemu.
    • Jeśli tak, zwróć wartość True.
    • W przeciwnym wypadku, jeśli element o środkowym indeksie jest mniejszy niż poszukiwany, ustaw indeks `początek` na `środek + 1`.
    • W przeciwnym wypadku, jeśli element o środkowym indeksie jest większy niż poszukiwany, ustaw indeks `koniec` na `środek – 1`.
    • Zwiększ wartość indeksu `i`.
  • Po zakończeniu pętli, jeśli funkcja nadal jest wykonywana, oznacza to, że element nie został znaleziony. W takim przypadku zwróć wartość False.
• Wyświetl komunikat na podstawie wartości zwróconej przez funkcję `szukaj_elementu`.

Spróbuj napisać kod, podobnie jak w przypadku implementacji algorytmu wyszukiwania liniowego.

…

Udało Ci się stworzyć kod?

Porównaj go z poniższym kodem. Jeżeli nie, nie przejmuj się. Przeanalizuj poniższy kod, aby zrozumieć jego działanie.

## funkcja wyszukiwania
def szukaj_elementu(posortowana_arr, n, element):

	## indeks tablicy do iteracji
	i = 0

	## zmienne do śledzenia zakresu wyszukiwania
	## inicjalizacja indeksami początkowym i końcowym
	start = 0
	end = n - 1

	## iteracja po tablicy
	while i < n:
		## obliczanie indeksu środkowego elementu
		middle = (start + end) // 2

		## sprawdzenie, czy środkowy element jest równy szukanemu
		if posortowana_arr[middle] == element:
			## zwrócenie True, ponieważ element znajduje się w tablicy
			return True
		elif posortowana_arr[middle] < element:
			## przesunięcie indeksu początkowego zakresu poszukiwań w prawo
			start = middle + 1
		else:
			## przesunięcie indeksu końcowego zakresu poszukiwań w lewo
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## inicjalizacja tablicy, długości i szukanego elementu
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_do_znalezienia = 9
	# element_do_znalezienia = 11

	if szukaj_elementu(arr, n, element_do_znalezienia):
		print(element_do_znalezienia, "został znaleziony")
	else:
		print(element_do_znalezienia, "nie został znaleziony")

Przeprowadź testy kodu, używając różnych przypadków, w których element jest obecny w tablicy oraz takich, w których element nie występuje.

Podsumowanie

Algorytm wyszukiwania binarnego jest znacznie bardziej wydajny niż algorytm wyszukiwania liniowego. W przypadku algorytmu wyszukiwania binarnego, konieczne jest posortowanie tablicy, co nie ma miejsca w przypadku algorytmu liniowego. Sortowanie wymaga czasu, jednakże zastosowanie wydajnych algorytmów sortowania, w połączeniu z algorytmem wyszukiwania binarnego, tworzy dobrą kombinację.

Teraz posiadasz dobrą wiedzę na temat najczęściej używanych algorytmów wyszukiwania w języku Python.

W dalszej kolejności zapoznaj się z popularnym oprogramowaniem wyszukiwania samoobsługowego.

Życzę miłego kodowania! 🙂 🧑‍💻