Implementări de algoritmi de căutare în Python

de
Tweet
Share
Share
Pin

Implementarea căutării este întotdeauna o provocare, dar nu imposibilă.

În viața reală, nu vom căuta în niciun model. Mergem doar în locurile unde credem că ar putea fi amplasat. În majoritatea cazurilor, nu urmăm niciun model.

Funcționează același lucru în lumea programării?

Nu! există un model pentru a căuta lucruri în programe. Vom vedea câțiva algoritmi care urmează modele diferite de căutare în acest articol.

Există mai mulți algoritmi pe care îi putem găsi în lumea programării. Vom discuta despre cei mai importanți și mai folosiți algoritmi în acest articol. Și restul algoritmilor va fi ușor de învățat.

Căutarea se referă la căutarea unui element din matricea din acest articol.

Să-i vedem unul câte unul.

Căutare liniară

Numele sugerează că algoritmul de căutare liniară urmează modelul liniar pentru a căuta elementele dintr-o matrice. Algoritmul începe să caute elementul de la începutul matricei și se deplasează până la sfârșit până găsește elementul. Oprește execuția programului când găsește elementul necesar.

Să ilustrăm algoritmii de căutare liniară cu câteva ilustrații interesante pentru o mai bună înțelegere a algoritmului.

Dacă observați cu atenție modelul de căutare, veți descoperi că timpul necesar pentru execuția programului va lua O(n) în cel mai rău caz. Trebuie să luăm în considerare complexitatea timpului în cel mai rău caz a algoritmilor de analizat. Prin urmare, complexitatea temporală a algoritmului este O(n).

Să vedem implementarea algoritmului de căutare liniară.

Implementarea Căutării Liniare

Acum, aveți o bună înțelegere a algoritmului de căutare liniară. Este timpul să ne murdărim mâinile cu niște coduri. Să vedem mai întâi pașii pentru a implementa căutarea liniară. Apoi încercați să îl codificați. Nu vă faceți griji chiar dacă nu puteți; Îți voi furniza codul după aceea.

  Cum să resetați BIOS-ul la setările implicite

Să vedem pașii pentru implementarea algoritmului de căutare liniară.

  • Inițializați o serie de elemente (numerele dvs. norocoase).
  • Scrieți o funcție numită element_căutare, care acceptă trei argumente, matrice, lungimea matricei și elementul de căutat.
  • element_căutare(arr, n, element):
    • Iterați peste matricea dată.
      • Verificați dacă elementul curent este egal cu elementul necesar.
      • Dacă da, atunci returnați True.
    • După finalizarea buclei, dacă execuția este încă în funcție, atunci elementul nu este prezent în matrice. Prin urmare, returnați False.
  • Imprimați mesajul pe baza valorii returnate a funcției search_element.

În cele din urmă, scrieți codul cu ajutorul pașilor de mai sus pentru a implementa algoritmul de căutare liniară.

Ați finalizat implementarea algoritmului de căutare liniară? Aşa sper. Dacă ați finalizat, verificați cu următorul cod.

Dacă nu l-ai completat, nu-ți face griji,; vedeți codul de mai jos și aflați cum l-am implementat. O vei obține fără prea mult efort.

## 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")

Mai întâi, executați programul cu un element care este prezent în matrice. Și apoi, executați-l cu un element care nu este prezent în matrice.

Complexitatea temporală a algoritmului de căutare liniară este O(n).

O putem reduce puțin mai mult cu diferite modele?

Da, putem. Să vedem.

Căutare binară

Algoritmul de căutare binar verifică întotdeauna elementul din mijloc al matricei. Acest algoritm caută elementul într-o matrice sortată.

Algoritmul de căutare binar iterează peste matrice și verifică elementul din mijloc, dacă este găsit, apoi oprește programul. În caz contrar, dacă elementul din mijloc este mai mic decât elementul necesar, atunci omite partea din stânga a matricei din elementul din mijloc de la căutare. În caz contrar, dacă elementul din mijloc este mai mare decât elementul necesar, atunci omite partea dreaptă a matricei din elementul din mijloc de la căutare.

  Cum să efectuați sarcini de administrare de bază pentru dispozitivele de stocare în Linux

În fiecare iterație, algoritmul de căutare binar reduce zona pentru a căuta elementul. Deci, numărul de verificări este mai mic decât numărul de verificări efectuate în algoritmul de căutare liniară.

Ilustrațiile ne ajută să înțelegem mai bine algoritmul de căutare binar. Să le verificăm.

Complexitatea temporală a algoritmului de căutare binar este O(log n). În fiecare iterație, lungimea zonei de căutare se reduce la jumătate. Se reduce exponențial.

Implementarea Căutării Binare

Mai întâi, vom vedea pașii pentru implementarea algoritmului de căutare binar și apoi codul. Să vedem pașii pentru a finaliza implementarea algoritmului de căutare binar.

  • Inițializați matricea cu elemente (numerele dvs. norocoase)
  • Scrieți o funcție numită element_căutare, care acceptă trei argumente, matrice sortată, lungimea matricei și elementul de căutat.
  • element_căutare(arr_sortat, n, element):
    • Inițializați variabila index i pentru iterația matricei.
    • Apoi, inițializați două variabile pentru a menține zona de căutare a matricei. Aici, le numim ca să înceapă și să se termine, deoarece indică indecși.
    • Iterați până când i este mai mic decât lungimea matricei.
      • Calculați indexul de mijloc al zonei de căutare folosind valorile de început și de sfârșit. Acesta va fi (început + sfârșit) // 2.
      • Verificați dacă elementul indexat din mijloc din zona de căutare este egal cu elementul necesar sau nu.
      • Dacă da, atunci returnați True.
      • Altfel, dacă elementul indexat din mijloc este mai mic decât elementul necesar, atunci mutați indexul de început al zonei de căutare la mijloc + 1.
      • Altfel, dacă elementul indexat din mijloc este mai mare decât elementul necesar, atunci mutați indexul final al zonei de căutare la mijloc – 1.
      • Incrementați indexul tabloului i.
    • După finalizarea buclei, dacă execuția este încă în funcție, atunci elementul nu este prezent în matrice. Prin urmare, returnați False.
  • Imprimați mesajul pe baza valorii returnate a funcției search_element.
  Cum să ascultați cărți audio gratuit pe Spotify

Încercați să scrieți codul similar cu implementarea algoritmului de căutare liniară.

…

Ai primit codul?

Da, comparați-l cu codul de mai jos. Nu, nu vă faceți griji; înțelegeți implementarea cu codul de mai jos.

## 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")

Testați codul cu diferite cazuri în care elementul este prezent și nu este prezent în unele cazuri.

Concluzie

Algoritmul de căutare binar este mult mai eficient decât algoritmul de căutare liniară. Trebuie să sortăm tabloul pentru algoritmul de căutare binar nu este cazul în algoritmul de căutare liniară. Sortarea durează ceva timp. Dar, utilizarea algoritmilor eficienți pentru sortare va forma o combinație bună cu algoritmul de căutare binar.

Acum, aveți o bună cunoaștere a celor mai folosiți algoritmi din Python.

Apoi, aflați câteva dintre cele mai populare programe de căutare auto-găzduite.

Codare fericită 🙂 🧑‍💻