Implementazioni di algoritmi di ricerca in Python

L’implementazione della ricerca è sempre impegnativa ma non impossibile.

Nella vita reale, non cercheremo in alcun modo. Andiamo solo nei luoghi in cui pensiamo possa essere collocato. Nella maggior parte dei casi non seguiamo alcuno schema.

Funziona la stessa cosa nel mondo della programmazione?

No! ci deve essere uno schema per cercare le cose nei programmi. Vedremo alcuni algoritmi che seguono diversi modelli per la ricerca in questo articolo.

Ci sono più algoritmi che possiamo trovare nel mondo della programmazione. Discuteremo gli algoritmi più importanti e maggiormente utilizzati in questo articolo. E il resto degli algoritmi sarà un gioco da ragazzi da imparare.

La ricerca si riferisce alla ricerca di un elemento nell’array in questo articolo.

Vediamoli uno per uno.

Ricerca lineare

Il nome suggerisce che l’algoritmo di ricerca lineare segue il modello lineare per cercare gli elementi in un array. L’algoritmo inizia la ricerca dell’elemento dall’inizio dell’array e si sposta alla fine finché non trova l’elemento. Interrompe l’esecuzione del programma quando trova l’elemento richiesto.

Illustriamo gli algoritmi di ricerca lineare con alcune fantastiche illustrazioni per una migliore comprensione dell’algoritmo.

Se osservi attentamente il modello di ricerca, scoprirai che il tempo impiegato per l’esecuzione del programma richiederà O(n) nel caso peggiore. Dobbiamo considerare la complessità temporale nel caso peggiore degli algoritmi da analizzare. Quindi la complessità temporale dell’algoritmo è O(n).

Vediamo l’implementazione dell’algoritmo di ricerca lineare.

Implementazione della ricerca lineare

Ora hai una buona conoscenza dell’algoritmo di ricerca lineare. È ora di sporcarci le mani con un po’ di codice. Vediamo prima i passaggi per implementare la ricerca lineare. Quindi provi a codificarlo. Non preoccuparti anche se non puoi; Ti fornirò il codice in seguito.

Vediamo i passaggi per implementare l’algoritmo di ricerca lineare.

• Inizializza un array di elementi (i tuoi numeri fortunati).
• Scrivete una funzione chiamata search_element, che accetti tre argomenti, array, lunghezza dell’array ed elemento da cercare.
• search_element(arr, n, elemento):
  • Iterare sull’array dato.
    • Controlla se l’elemento corrente è uguale all’elemento richiesto.
    • Se sì, restituisci True.
  • Dopo aver completato il ciclo, se l’esecuzione è ancora nella funzione, allora l’elemento non è presente nell’array. Quindi restituisci Falso.
• Stampa il messaggio in base al valore restituito dalla funzione elemento_ricerca.

Infine, scrivi il codice con l’aiuto dei passaggi precedenti per implementare l’algoritmo di ricerca lineare.

Hai completato l’implementazione dell’algoritmo di ricerca lineare? Lo spero. Se hai completato, fai un controllo incrociato con il codice seguente.

Se non l’hai completato, non preoccuparti; guarda il codice qui sotto e scopri come lo abbiamo implementato. Lo otterrai senza troppi sforzi.

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

Innanzitutto, esegui il programma con un elemento presente nell’array. E poi, eseguilo con un elemento che non è presente nell’array.

La complessità temporale dell’algoritmo di ricerca lineare è O(n).

Possiamo ridurlo un po ‘di più con modelli diversi?

Sì, possiamo. Vediamolo.

Ricerca binaria

L’algoritmo di ricerca binaria controlla sempre l’elemento centrale dell’array. Questo algoritmo cerca l’elemento in un array ordinato.

L’algoritmo di ricerca binaria itera sull’array e controlla l’elemento centrale, se trovato, quindi interrompe il programma. Altrimenti, se l’elemento centrale è inferiore all’elemento richiesto, omette la parte sinistra dell’array dall’elemento centrale dalla ricerca. Altrimenti, se l’elemento centrale è maggiore dell’elemento richiesto, omette la parte destra dell’array dall’elemento centrale dalla ricerca.

In ogni iterazione, l’algoritmo di ricerca binaria riduce l’area per cercare l’elemento. Quindi, il numero di controlli è inferiore al numero di controlli effettuati nell’algoritmo di ricerca lineare.

Le illustrazioni ci aiutano a comprendere meglio l’algoritmo di ricerca binaria. Controlliamoli.

La complessità temporale dell’algoritmo di ricerca binaria è O(log n). In ogni iterazione, la lunghezza dell’area di ricerca si riduce della metà. Sta diminuendo esponenzialmente.

Implementazione della ricerca binaria

Innanzitutto, vedremo i passaggi per implementare l’algoritmo di ricerca binaria e quindi il codice. Vediamo i passaggi per completare l’implementazione dell’algoritmo di ricerca binaria.

• Inizializza l’array con elementi (i tuoi numeri fortunati)
• Scrivete una funzione chiamata elemento_ricerca, che accetti tre argomenti, un array ordinato, la lunghezza dell’array e l’elemento da cercare.
• search_element(sorted_arr, n, element):
  • Inizializza la variabile indice i per l’iterazione dell’array.
  • Successivamente, inizializza due variabili per mantenere l’area di ricerca dell’array. Qui li chiamiamo come inizio e fine in quanto indicano gli indici.
  • Itera fino a quando i è minore della lunghezza dell’array.
    • Calcola l’indice centrale dell’area di ricerca utilizzando i valori iniziale e finale. Sarà (inizio + fine) // 2.
    • Controlla se l’elemento centrale indicizzato dall’area di ricerca è uguale o meno all’elemento richiesto.
    • Se sì, restituisci True.
    • Altrimenti, se l’elemento indicizzato centrale è inferiore all’elemento richiesto, sposta l’indice iniziale dell’area di ricerca al centro + 1.
    • Altrimenti, se l’elemento indicizzato centrale è maggiore dell’elemento richiesto, sposta l’indice finale dell’area di ricerca al centro – 1.
    • Incrementa l’indice dell’array i.
  • Dopo aver completato il ciclo, se l’esecuzione è ancora nella funzione, allora l’elemento non è presente nell’array. Quindi restituisci Falso.
• Stampa il messaggio in base al valore restituito dalla funzione elemento_ricerca.

Prova a scrivere il codice in modo simile all’implementazione dell’algoritmo di ricerca lineare.

…

Hai ricevuto il codice?

Sì, confrontalo con il codice qui sotto. No, non preoccuparti; comprendere l’implementazione con il codice seguente.

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

Testare il codice con diversi casi in cui l’elemento è presente e non presente in alcuni casi.

Conclusione

L’algoritmo di ricerca binaria è molto più efficiente dell’algoritmo di ricerca lineare. Dobbiamo ordinare l’array per l’algoritmo di ricerca binaria non è il caso dell’algoritmo di ricerca lineare. L’ordinamento richiede del tempo. Tuttavia, l’utilizzo di algoritmi efficienti per l’ordinamento formerà una buona combinazione con l’algoritmo di ricerca binaria.

Ora hai una buona conoscenza degli algoritmi più utilizzati in Python.

Successivamente, scopri alcuni dei popolari software di ricerca self-hosted.

Buona programmazione 🙂 🧑‍💻