Recherche linéaire en Python
La recherche linéaire fonctionne sur des données non triées.
Qu’est-ce que la recherche linéaire ?
La recherche linéaire examine chaque élément depuis le début jusqu’à trouver la cible ou atteindre la fin. Les données n’ont pas besoin d’être triées.
Fonctionnement de l’algorithme
- Commencer à l’indice 0.
- Comparer l’élément courant à la cible.
- Renvoyer son indice en cas d’égalité, sinon continuer.
- Renvoyer -1 après le dernier élément si la cible est absente.
Complexité : O(n) en temps dans les cas moyen et défavorable, avec O(1) d’espace supplémentaire.
Visualisation de Recherche linéaire en Python
O(n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
main.py
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))Résultat attendu
3Fonctionnement
Chaque valeur est comparée une fois au maximum : temps O(n), mémoire O(1).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices pratiques
Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.
- Testez une entrée vide, un élément et des doublons.
- Affichez l’état après chaque étape.
- Comparez les performances avec une autre solution.