Résumé complet : Recherche linéaire

Recherche Linéaire

Recherche_{linéaire}(n) = O(n)

Exploration séquentielle de la structure

Définition :

            Recherche linéaire : algorithme qui parcourt une structure de données séquentiellement pour trouver un élément particulier en comparant chaque élément avec la cible.

Principe :

🔁 Parcours de gauche à droite
↔️ Comparaison avec cible
🎯 Arrêt dès trouvaille
📋 Taux de succès variable

Complexité :

✅ Meilleur cas : O(1)
❌ Pire cas : O(n)
📊 Moyen : O(n)

Algorithme de recherche

🔍

Itération : parcours séquentiel

✅

Comparaison : élément = cible

🎯

Retour : position ou -1

📊

Évaluation : efficacité

Étapes de l'algorithme

1️⃣

Initialiser l'indice à 0

2️⃣

Comparer élément à la cible

3️⃣

Avancer ou retourner position

Implémentation

🔄

Version itérative

🎯

Version avec indice

✅

Gestion absence

💡

Améliorations possibles

Code de l'algorithme

def recherche_lineaire(L, cible):
    """
    Recherche la cible dans la liste L
    Retourne l'indice si trouvé, -1 sinon
    """
    for i in range(len(L)):
        if L[i] == cible:
            return i
    return -1

# Exemple
liste = [10, 25, 3, 47, 15]
position = recherche_lineaire(liste, 47)  # Retourne 3
        

Applications

🔍

Recherche simple : petite liste

📊

Validation : présence élément

🔄

Base : pour autres algorithmes

Erreurs fréquentes

Erreur 1 :

Boucle mal bornée
for i in range(len(L)+1): # Trop loin!
for i in range(len(L)): # Correct

Erreur 2 :

Oublier la condition d'arrêt
while i < len(L):
    if L[i] == cible:
        return i
    i += 1 # Important!

Erreur 3 :

Retourner position sans vérification
if L[i] == cible: return i # OK
else: return -1 # Problème - arrête au premier élément