Ricerca lineare in Python
Harshit Jindal
3 gennaio 2023
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).
Autore: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn