HOWTO · Python
Ricerca lineare in Python
Questo tutorial introduce l'algoritmo di ricerca lineare implementato in Python.
In questa pagina
Nota
Se si desidera comprendere in dettaglio la ricerca lineare, fare riferimento all’articolo Algoritmo di ricerca lineare.
Algoritmo di ricerca lineare
Supponiamo di avere un array non ordinato A[] contenente n elementi e di voler trovare un elemento - X.
-
Attraversa tutti gli elementi all’interno dell’array partendo dall’elemento più a sinistra usando un cicli
fore fai quanto segue:- Se il valore di
A[i]corrisponde aX, restituisci l’indicei. (Se possono esserci più elementi che corrispondono aX, invece di restituire l’indicei, stampa tutti gli indici o memorizza tutti gli indici in un array e restituisci quell’array.) - Altrimenti passa all’elemento successivo.
- Se si trova all’ultimo elemento dell’array, esci dal cicli
for.
- Se il valore di
-
Se nessuno degli elementi corrisponde, restituisce
-1.
Implementazione di Python per la ricerca lineare
def linearsearch(arr, n, x):
for i in range(0, n):
if arr[i] == x:
return i
return -1
arr = [1, 2, 3, 4, 5]
x = 1
n = len(arr)
position = linearsearch(arr, n, x)
if position == -1:
print("Element not found !!!")
else:
print("Element is present at index", position)
Produzione:
Element is found at index: 1
La complessità temporale dell’algoritmo di cui sopra è O(n).
