Implementacje algorytmów wyszukiwania w języku Python

Implementacja wyszukiwania jest zawsze trudna, ale nie niemożliwa.

W prawdziwym życiu będziemy szukać bez schematu. Po prostu idziemy do miejsc, w których naszym zdaniem może być umieszczony. W większości przypadków nie podążamy za żadnym schematem.

Czy to samo działa w świecie programowania?

Nie! musi być jakiś wzorzec wyszukiwania rzeczy w programach. W tym artykule zobaczymy kilka algorytmów, które stosują różne wzorce wyszukiwania.

Istnieje wiele algorytmów, które możemy znaleźć w świecie programowania. W tym artykule omówimy najważniejsze i najczęściej używane algorytmy. A reszta algorytmów będzie dla ciebie bułką z masłem do nauczenia.

Wyszukiwanie odnosi się do wyszukiwania elementu w tablicy w tym artykule.

Zobaczmy je jeden po drugim.

Wyszukiwanie liniowe

Nazwa sugeruje, że algorytm wyszukiwania liniowego podąża za wzorcem liniowym, aby przeszukiwać elementy w tablicy. Algorytm rozpoczyna wyszukiwanie elementu od początku tablicy i przesuwa się do końca, aż znajdzie element. Zatrzymuje wykonywanie programu, gdy znajdzie wymagany element.

Zilustrujmy algorytmy wyszukiwania liniowego kilkoma fajnymi ilustracjami, aby lepiej zrozumieć algorytm.

Jeśli uważnie przyjrzysz się wzorcowi wyszukiwania, zauważysz, że czas potrzebny na wykonanie programu wyniesie O(n) w najgorszym przypadku. Musimy wziąć pod uwagę złożoność czasową analizowanych algorytmów w najgorszym przypadku. Stąd złożoność czasowa algorytmu wynosi O(n).

Zobaczmy implementację algorytmu wyszukiwania liniowego.

Implementacja wyszukiwania liniowego

Teraz dobrze rozumiesz algorytm wyszukiwania liniowego. Czas pobrudzić sobie ręce jakimś kodem. Zobaczmy najpierw, jak zaimplementować wyszukiwanie liniowe. Następnie próbujesz go zakodować. Nie martw się, nawet jeśli nie możesz; Kod podam później.

Zobaczmy, jak zaimplementować algorytm wyszukiwania liniowego.

  • Zainicjuj tablicę elementów (twoje szczęśliwe liczby).
  • Napisz funkcję o nazwie element_wyszukiwania, która przyjmuje trzy argumenty, tablicę, długość tablicy i element do przeszukania.
  • element_wyszukiwania(tablica, n, element):
    • Iteruj po podanej tablicy.
      • Sprawdź, czy bieżący element jest równy wymaganemu elementowi.
      • Jeśli tak, zwróć True.
    • Po zakończeniu pętli, jeśli wykonanie jest nadal w funkcji, oznacza to, że elementu nie ma w tablicy. Stąd zwróć Fałsz.
  • Wydrukuj komunikat na podstawie wartości zwracanej przez funkcję search_element.

Na koniec napisz kod za pomocą powyższych kroków, aby zaimplementować algorytm wyszukiwania liniowego.

Czy zakończyłeś implementację algorytmu wyszukiwania liniowego? Mam nadzieję. Jeśli zakończyłeś, sprawdź krzyżowo z następującym kodem.

Jeśli go nie ukończyłeś, nie martw się; zobacz poniższy kod i dowiedz się, jak go zaimplementowaliśmy. Osiągniesz to bez większego wysiłku.

## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Najpierw wykonaj program z elementem obecnym w tablicy. A następnie wykonaj go z elementem, którego nie ma w tablicy.

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

Czy możemy go jeszcze bardziej zredukować za pomocą innych wzorów?

Tak, możemy. Zobaczmy.

Wyszukiwanie binarne

Algorytm wyszukiwania binarnego zawsze sprawdza środkowy element tablicy. Algorytm ten wyszukuje element w posortowanej tablicy.

Algorytm wyszukiwania binarnego iteruje po tablicy i sprawdza środkowy element, jeśli został znaleziony, a następnie zatrzymuje program. W przeciwnym razie, jeśli środkowy element jest mniejszy niż wymagany element, pomija lewą część tablicy ze środkowego elementu podczas wyszukiwania. W przeciwnym razie, jeśli środkowy element jest większy niż wymagany element, pomija prawą część tablicy ze środkowego elementu podczas wyszukiwania.

W każdej iteracji algorytm wyszukiwania binarnego zmniejsza obszar wyszukiwania elementu. Tak więc liczba kontroli jest mniejsza niż liczba kontroli wykonanych w algorytmie wyszukiwania liniowego.

Ilustracje pomagają nam lepiej zrozumieć algorytm wyszukiwania binarnego. Sprawdźmy je.

Złożoność czasowa algorytmu wyszukiwania binarnego wynosi O (log n). W każdej iteracji długość obszaru poszukiwań zmniejsza się o połowę. Zmniejsza się wykładniczo.

Implementacja wyszukiwania binarnego

Najpierw zobaczymy kroki, aby zaimplementować algorytm wyszukiwania binarnego, a następnie kod. Zobaczmy, jak zakończyć implementację algorytmu wyszukiwania binarnego.

  • Zainicjuj tablicę elementami (twoje szczęśliwe liczby)
  • Napisz funkcję o nazwie element_wyszukiwania, która przyjmuje trzy argumenty, posortowaną tablicę, długość tablicy i element do przeszukania.
  • search_element(sorted_arr, n, element):
    • Zainicjuj zmienną indeksu i dla iteracji tablicy.
    • Następnie zainicjuj dwie zmienne, aby zachować obszar wyszukiwania tablicy. Tutaj nazywamy je tak, aby zaczynały się i kończyły, ponieważ wskazują indeksy.
    • Iteruj, aż i będzie mniejsze niż długość tablicy.
      • Oblicz środkowy indeks obszaru wyszukiwania, używając wartości początkowej i końcowej. To będzie (początek + koniec) // 2.
      • Sprawdź, czy środkowy indeksowany element z obszaru wyszukiwania jest równy wymaganemu elementowi, czy nie.
      • Jeśli tak, zwróć True.
      • W przeciwnym razie, jeśli środkowy indeksowany element jest mniejszy niż wymagany element, przenieś początkowy indeks obszaru wyszukiwania do środka + 1.
      • W przeciwnym razie, jeśli środkowy element indeksowany jest większy niż wymagany element, przenieś indeks końcowy obszaru wyszukiwania na środek – 1.
      • Zwiększ indeks tablicy i.
    • Po zakończeniu pętli, jeśli wykonanie jest nadal w funkcji, oznacza to, że elementu nie ma w tablicy. Stąd zwróć Fałsz.
  • Wydrukuj komunikat na podstawie wartości zwracanej przez funkcję search_element.

Spróbuj napisać kod podobny do implementacji algorytmu wyszukiwania liniowego.

Dostałeś kod?

Tak, porównaj to z poniższym kodem. Nie, nie martw się; zrozumieć implementację za pomocą poniższego kodu.

## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Przetestuj kod z różnymi przypadkami, w których element jest obecny i nie występuje w niektórych przypadkach.

Wniosek

Algorytm wyszukiwania binarnego jest znacznie bardziej wydajny niż algorytm wyszukiwania liniowego. Musimy posortować tablicę dla algorytmu wyszukiwania binarnego, co nie ma miejsca w przypadku algorytmu wyszukiwania liniowego. Sortowanie zajmuje trochę czasu. Ale użycie wydajnych algorytmów do sortowania będzie stanowić dobrą kombinację z algorytmem wyszukiwania binarnego.

Teraz masz dobrą znajomość najczęściej używanych algorytmów w Pythonie.

Następnie zapoznaj się z popularnym samoobsługowym oprogramowaniem do wyszukiwania.

Miłego kodowania 🙂 🧑‍💻