HOWTO · Python
Recherche linéaire en Python
Ce didacticiel présente l'algorithme de recherche linéaire implémenté en Python.
Sur cette page
Note
Si vous voulez comprendre la recherche linéaire en détail, reportez-vous à l’article Recherche linéaire.
Algorithme de recherche linéaire
Supposons que nous ayons un tableau non trié A[] contenant n éléments, et nous voulons trouver un élément - X.
-
Traverse tous les éléments à l’intérieur du tableau en commençant par l’élément le plus à gauche en utilisant une boucle
foret procédez comme suit:- Si la valeur de
A[i]correspond àX, alors renvoie l’indexi. (S’il peut y avoir plusieurs éléments correspondant àX, alors au lieu de renvoyer l’indexi, imprimez tous les index ou stockez tous les index dans un tableau et renvoyez ce tableau.) - Sinon, passez à l’élément suivant.
- S’il se trouve au dernier élément du tableau, quittez la boucle
for.
- Si la valeur de
-
Si aucun des éléments ne correspond, alors renvoie
-1.
Implémentation Python de recherche linéaire
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)
Production:
Element is found at index: 1
La complexité temporelle de l’algorithme ci-dessus est O(n).
