Implementace vyhledávacích algoritmů v Pythonu

autor:
Tweet
Share
Share
Pin

Zavedení vyhledávání je vždy náročné, ale ne nemožné.

V reálném životě nebudeme hledat žádný vzor. Prostě jdeme na místa, kde si myslíme, že by to mohlo být umístěno. Ve většině případů se neřídíme žádným vzorem.

Funguje to samé ve světě programování?

Ne! tam musí být nějaký vzor pro vyhledávání věcí v programech. V tomto článku uvidíme některé algoritmy, které se při vyhledávání řídí různými vzory.

Ve světě programování můžeme najít několik algoritmů. V tomto článku se budeme zabývat nejdůležitějšími a nejčastěji používanými algoritmy. A zbytek algoritmů bude hračka, kterou se pro vás naučíte.

Hledání odkazuje na hledání prvku v poli v tomto článku.

Podívejme se na ně jednoho po druhém.

Lineární vyhledávání

Název napovídá, že lineární vyhledávací algoritmus sleduje lineární vzor pro vyhledávání prvků v poli. Algoritmus začne prohledávat prvek od začátku pole a přesouvá se na konec, dokud prvek nenajde. Zastaví provádění programu, když nalezne požadovaný prvek.

Pojďme ilustrovat lineární vyhledávací algoritmy pomocí několika skvělých ilustrací pro lepší pochopení algoritmu.

Pokud budete pečlivě sledovat vyhledávací vzorec, zjistíte, že čas potřebný k provedení programu bude v nejhorším případě trvat O(n). Musíme vzít v úvahu nejhorší případ časové složitosti analyzovaných algoritmů. Časová složitost algoritmu je tedy O(n).

Podívejme se na implementaci lineárního vyhledávacího algoritmu.

Implementace lineárního vyhledávání

Nyní již dobře rozumíte lineárnímu vyhledávacímu algoritmu. Je čas ušpinit si ruce nějakým kódem. Nejprve se podívejme na kroky k implementaci lineárního vyhledávání. Pak to zkus nakódovat. Nedělejte si starosti, i když nemůžete; Poté vám poskytnu kód.

  Porozumění půjčování a půjčování kryptoměn pro začátečníky

Podívejme se na kroky k implementaci lineárního vyhledávacího algoritmu.

  • Inicializujte pole prvků (vaše šťastná čísla).
  • Napište funkci s názvem search_element, která přijímá tři argumenty, pole, délku pole a prvek, který se má prohledat.
  • search_element(arr, n, element):
    • Iterujte přes dané pole.
      • Zkontrolujte, zda se aktuální prvek rovná požadovanému prvku.
      • Pokud ano, vraťte True.
    • Pokud je po dokončení cyklu provádění stále ve funkci, prvek není v poli přítomen. Proto návrat False.
  • Vytiskněte zprávu na základě návratové hodnoty funkce search_element.

Nakonec zapište kód pomocí výše uvedených kroků, abyste implementovali algoritmus lineárního vyhledávání.

Dokončili jste implementaci lineárního vyhledávacího algoritmu? Doufám. Pokud jste dokončili, zkontrolujte pomocí následujícího kódu.

Pokud jste to nedokončili, nebojte se,; podívejte se na níže uvedený kód a zjistěte, jak jsme jej implementovali. Získáte to bez velkého úsilí.

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

Nejprve spusťte program s prvkem, který je přítomen v poli. A poté jej spusťte s prvkem, který není přítomen v poli.

Časová složitost lineárního vyhledávacího algoritmu je O(n).

Můžeme to ještě trochu zmenšit pomocí různých vzorů?

Ano, můžeme. Pojďme se na to podívat.

Binární vyhledávání

Binární vyhledávací algoritmus vždy kontroluje prostřední prvek pole. Tento algoritmus prohledává prvek v seřazeném poli.

  Jak hledat někoho na Match.com podle uživatelského jména

Binární vyhledávací algoritmus iteruje pole a zkontroluje prostřední prvek, je-li nalezen, pak zastaví program. V opačném případě, pokud je prostřední prvek menší než požadovaný prvek, vynechá z vyhledávání levou část pole ze prostředního prvku. V opačném případě, pokud je prostřední prvek větší než požadovaný prvek, vynechá z vyhledávání pravou část pole ze prostředního prvku.

V každé iteraci binární vyhledávací algoritmus omezí oblast pro prohledání prvku. Počet kontrol je tedy menší než počet kontrol provedených v lineárním vyhledávacím algoritmu.

Ilustrace nám pomáhají lépe porozumět binárnímu vyhledávacímu algoritmu. Pojďme je zkontrolovat.

Časová složitost binárního vyhledávacího algoritmu je O(log n). V každé iteraci se délka prohledávané oblasti zkracuje na polovinu. Snižuje se exponenciálně.

Implementace binárního vyhledávání

Nejprve uvidíme kroky k implementaci binárního vyhledávacího algoritmu a poté kód. Podívejme se na kroky k dokončení implementace binárního vyhledávacího algoritmu.

  • Inicializujte pole pomocí prvků (vaše šťastná čísla)
  • Napište funkci s názvem search_element, která přijímá tři argumenty, seřazené pole, délku pole a prvek, který se má prohledat.
  • search_element(sorted_arr, n, element):
    • Inicializujte proměnnou indexu i pro iteraci pole.
    • Dále inicializujte dvě proměnné, aby se zachovala oblast hledání pole. Zde je nazýváme jako začátek a konec, protože označují indexy.
    • Opakujte, dokud nebude i menší než délka pole.
      • Vypočítejte střední index oblasti hledání pomocí počáteční a koncové hodnoty. To bude (začátek + konec) // 2.
      • Zkontrolujte, zda se prostřední indexovaný prvek z oblasti vyhledávání rovná požadovanému prvku nebo ne.
      • Pokud ano, vraťte True.
      • V opačném případě, pokud je prostřední indexovaný prvek menší než požadovaný prvek, přesuňte počáteční index oblasti vyhledávání na střed + 1.
      • V opačném případě, pokud je prostřední indexovaný prvek větší než požadovaný prvek, přesuňte koncový index oblasti vyhledávání na střed – 1.
      • Zvyšte index pole i.
    • Pokud je po dokončení cyklu provádění stále ve funkci, prvek není v poli přítomen. Proto návrat False.
  • Vytiskněte zprávu na základě návratové hodnoty funkce search_element.
  Jak zkontrolovat procento baterie iPhone X

Pokuste se napsat kód podobný implementaci lineárního vyhledávacího algoritmu.

…

Získali jste kód?

Ano, porovnejte to s níže uvedeným kódem. Ne, nebojte se; pochopit implementaci pomocí níže uvedeného kódu.

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

Testujte kód s různými případy, kdy je prvek přítomen a v některých případech není přítomen.

Závěr

Binární vyhledávací algoritmus je mnohem efektivnější než lineární vyhledávací algoritmus. Potřebujeme třídit pole pro binární vyhledávací algoritmus, což není případ lineárního vyhledávacího algoritmu. Třídění nějakou dobu trvá. Ale použití efektivních algoritmů pro třídění bude tvořit dobrou kombinaci s binárním vyhledávacím algoritmem.

Nyní máte dobrou znalost nejpoužívanějších algoritmů v Pythonu.

Dále zjistěte některé z populárního vyhledávacího softwaru s vlastním hostitelem.

Veselé kódování 🙂 🧑‍💻