Recherche linéaire | Exercices corrigés

Concepts & Exercices

\(\text{Recherche}(T, x) \rightarrow i \text{ ou } -1\)

Recherche d'un élément dans un tableau

Complexité

O(n)

Linéaire

Pire cas

Itérations

Meilleur cas

Itération

🎯

Définition : La recherche linéaire parcourt un tableau élément par élément.

📏

Principe : Comparer chaque élément avec la cible jusqu'à trouver une correspondance.

📋

Retour : L'indice de l'élément trouvé ou -1 si absent.

⚡

Utilité : Simple, fonctionne sur tableaux non triés.

💡

Conseil : Utilisez la recherche linéaire pour les petits tableaux ou non triés

🔍

Attention : La complexité est O(n) dans le pire des cas

⚡

Astuce : S'arrête dès qu'un élément est trouvé

📋

Méthode : Parcourez de gauche à droite jusqu'à la fin ou la cible

Exercice 1

Recherche d'un élément dans un tableau d'entiers

Exercice 2

Recherche dans un tableau de chaînes de caractères

Exercice 3

Recherche du premier élément satisfaisant un critère

Exercice 4

Analyse de la complexité de la recherche linéaire

Exercice 5

Application à des données réelles

Corrigé : Exercices 1 à 3

1 Recherche d'un entier

Définition :

Recherche linéaire : Algorithme qui examine chaque élément d'une structure séquentiellement.

Objectif : Trouver un élément spécifique ou déterminer s'il est présent.

Méthode de recherche linéaire :

Initialiser un compteur d'itération à 0
Parcourir le tableau de gauche à droite
Comparer chaque élément avec la cible
Retourner l'indice si trouvé, continuer sinon
Retourner -1 si la fin du tableau est atteinte sans succès

Tableau

T = [4, 2, 7, 1, 9, 3]

Cible

x = 7

Résultat

i = 2

Étape 1 : Initialisation

Tableau T = [4, 2, 7, 1, 9, 3] - Taille n = 6

Cible x = 7 - Indice initial i = 0

Étape 2 : Itération 1 (i=0)

T[0] = 4 - Comparaison : 4 == 7 ? Non

Passer à l'élément suivant

Étape 3 : Itération 2 (i=1)

T[1] = 2 - Comparaison : 2 == 7 ? Non

Passer à l'élément suivant

Étape 4 : Itération 3 (i=2)

T[2] = 7 - Comparaison : 7 == 7 ? Oui

Élément trouvé ! Retourner l'indice 2

Itération	Indice	Élément	Comparaison	Terminé
1	0	4	4≠7	false
2	1	2	2≠7	false
3	2	7	7=7 ✓	true

                // Pseudo-code
                fonction recherche_lineaire(T, x):
                  pour i de 0 à longueur(T)-1:
                    si T[i] == x:
                      retourner i
                  retourner -1
              

Résultat = 2

Réponse finale :

L'élément 7 est trouvé à l'indice 2 dans le tableau [4, 2, 7, 1, 9, 3].

Règles appliquées :

• Recherche linéaire : Parcours séquentiel de la structure

• Arrêt anticipé : S'arrête dès que l'élément est trouvé

• Valeur de retour : Indice si trouvé, -1 sinon

2 Recherche dans chaînes

Définition :

Recherche dans chaînes : Extension de la recherche linéaire aux tableaux de chaînes.

Comparaison : Utilisation de l'égalité de chaînes pour la correspondance.

Tableau

Noms = ["Alice", "Bob", "Charlie", "David"]

Cible

x = "Charlie"

Résultat

i = 2

Alice

Bob

Charlie

David

Étape 1 : Analyse du tableau

Tableau Noms = ["Alice", "Bob", "Charlie", "David"] - 4 éléments

Cible x = "Charlie"

Étape 2 : Itération 1 (i=0)

Noms[0] = "Alice" - Comparaison : "Alice" == "Charlie" ? Non

Étape 3 : Itération 2 (i=1)

Noms[1] = "Bob" - Comparaison : "Bob" == "Charlie" ? Non

Étape 4 : Itération 3 (i=2)

Noms[2] = "Charlie" - Comparaison : "Charlie" == "Charlie" ? Oui

Élément trouvé ! Retourner l'indice 2

Itération	Indice	Nom	Comparaison
1	0	"Alice"	"Alice"≠"Charlie"
2	1	"Bob"	"Bob"≠"Charlie"
3	2	"Charlie"	"Charlie"="Charlie" ✓

                // Pseudo-code
                fonction recherche_chaine(noms, cible):
                  pour i de 0 à longueur(noms)-1:
                    si noms[i] == cible:
                      retourner i
                  retourner -1
                  
                noms = ["Alice", "Bob", "Charlie", "David"]
                resultat = recherche_chaine(noms, "Charlie")
                // resultat = 2
              

Résultat = 2

Réponse finale :

"Charlie" est trouvé à l'indice 2 dans le tableau ["Alice", "Bob", "Charlie", "David"].

Règles appliquées :

• Chaînes de caractères : Comparaison exacte avec l'opérateur ==

• Sensibilité : La comparaison est sensible à la casse

• Performance : La complexité reste O(n) indépendamment du type

3 Recherche par critère

Définition :

Recherche par critère : Trouver le premier élément satisfaisant une condition.

Predicate : Fonction booléenne qui teste la condition sur chaque élément.

Tableau

T = [4, 2, 7, 1, 9, 3]

Critère

x > 5

Résultat

i = 2

Étape 1 : Définition du critère

Nous cherchons le premier élément strictement supérieur à 5

Fonction prédicat : f(x) = x > 5

Étape 2 : Itération 1 (i=0)

T[0] = 4 - Test : 4 > 5 ? Non

Passer à l'élément suivant

Étape 3 : Itération 2 (i=1)

T[1] = 2 - Test : 2 > 5 ? Non

Passer à l'élément suivant

Étape 4 : Itération 3 (i=2)

T[2] = 7 - Test : 7 > 5 ? Oui

Élément trouvé ! Retourner l'indice 2

Itération	Indice	Élément	Critère (x>5)	Terminé
1	0	4	false	false
2	1	2	false	false
3	2	7	true ✓	true

                // Pseudo-code
                fonction recherche_critere(T, predicat):
                  pour i de 0 à longueur(T)-1:
                    si predicat(T[i]):
                      retourner i
                  retourner -1
                  
                tableau = [4, 2, 7, 1, 9, 3]
                resultat = recherche_critere(tableau, lambda x: x > 5)
                // resultat = 2 (pour l'élément 7)
              

Premier élément > 5 : 7 à l'indice 2

Réponse finale :

Le premier élément supérieur à 5 est 7, à l'indice 2.

Règles appliquées :

• Critère personnalisé : Utilisation d'une fonction prédicat

• Arrêt anticipé : S'arrête au premier élément satisfaisant le critère

• Flexibilité : Adaptation à divers types de conditions

Corrigé : Exercices 4 à 5

4 Analyse de complexité

Définition :

Complexité algorithmique : Mesure de la performance en fonction de la taille des données.

Notation O : Bornes supérieures asymptotiques des ressources nécessaires.

Algo

Recherche linéaire

Comp

O(n)

Cas

Pire cas = n

Étape 1 : Analyse du meilleur cas

Élément cible à la position 0

1 seule comparaison → Complexité O(1)

Étape 2 : Analyse du cas moyen

Élément cible au milieu du tableau en moyenne

n/2 comparaisons en moyenne → Complexité O(n)

Étape 3 : Analyse du pire cas

Élément cible à la dernière position ou absent

n comparaisons dans le pire cas → Complexité O(n)

Étape 4 : Conclusion sur la complexité

Quel que soit le cas, la complexité est proportionnelle à n

Donc la complexité de la recherche linéaire est O(n)

Scénario	Comparaisons	Complexité
Meilleur cas	1	O(1)
Cas moyen	n/2	O(n)
Pire cas	n	O(n)

\(\text{Comparaisons}_{\text{moyennes}} = \frac{n+1}{2}\)

Nombre moyen de comparaisons

Complexité = O(n)

Réponse finale :

La complexité de la recherche linéaire est O(n) dans le pire des cas.

Règles appliquées :

• Complexité : Analyser le nombre d'opérations en fonction de la taille

• Pire cas : Important pour garantir une performance minimale

• Comparaison : O(n) est acceptable pour de petites structures

5 Application à des données réelles

Définition :

Application concrète : Utilisation de la recherche linéaire sur des données du monde réel.

Contexte : Recherche de produits, d'employés, de données scientifiques.

Données

Produits = ["Pomme", "Banane", "Orange", "Pêche"]

Recherche

x = "Orange"

Résultat

i = 2

Étape 1 : Contexte de l'application

Magasin avec une liste de produits disponibles

Nous voulons vérifier si "Orange" est en stock

Étape 2 : Application de la recherche

Liste produits = ["Pomme", "Banane", "Orange", "Pêche"]

Recherche de "Orange" → Trouvé à l'indice 2

Étape 3 : Interprétation des résultats

Orange est disponible en stock (position 2)

Temps de recherche : 3 comparaisons (rapide pour une petite liste)

Étape 4 : Analyse de performance

Pour 4 produits : maximum 4 comparaisons

La recherche linéaire est appropriée pour cette taille

Position	Produit	Recherche "Orange"	Stock
0	Pomme	Non	Disponible
1	Banane	Non	Disponible
2	Orange	Oui ✓	Disponible
3	Pêche	Non	Disponible

                // Application en Python
                def recherche_produit(stock, produit_recherche):
                  for i in range(len(stock)):
                    if stock[i] == produit_recherche:
                      return i
                  return -1
                
                produits = ["Pomme", "Banane", "Orange", "Pêche"]
                position = recherche_produit(produits, "Orange")
                
                if position != -1:
                  print(f"'Orange' est en stock à la position {position}")
                else:
                  print("'Orange' n'est pas en stock")
                
                # Affiche: 'Orange' est en stock à la position 2
              

Orange trouvé à l'indice 2

Réponse finale :

"Orange" est en stock à la position 2 dans la liste des produits.

Règles appliquées :

• Application : La recherche linéaire est utile pour des données réelles

• Performance : Adaptée aux petites structures de données

• Utilité : Validation de présence dans une collection

Cours bien détaillé

\(\text{Recherche}(T, x) = O(n)\)

Complexité de la recherche linéaire

🎯

Définition : La recherche linéaire parcourt un tableau élément par élément.

📏

Principe : Comparer chaque élément avec la cible jusqu'à trouver une correspondance.

📋

Retour : L'indice de l'élément trouvé ou -1 si absent.

⚡

Utilité : Simple, fonctionne sur tableaux non triés.

💡

Conseil : Utilisez la recherche linéaire pour les petits tableaux ou non triés

🔍

Attention : La complexité est O(n) dans le pire des cas

⚡

Astuce : S'arrête dès qu'un élément est trouvé

📋

Méthode : Parcourez de gauche à droite jusqu'à la fin ou la cible

✅

Vérification : Testez avec des cas limites (absent, premier, dernier)

🔄

Amélioration : Pour de grandes données, utilisez la recherche dichotomique

Implémentation de la recherche linéaire :

Version simple : Recherche d'égalité exacte
Version générique : Avec fonction prédicat pour critères personnalisés
Version avec compteur : Suivi du nombre de comparaisons
Optimisation : Vérifier si le tableau est vide avant de commencer

Règles importantes :

La complexité de la recherche linéaire est O(n) dans le pire des cas
Elle fonctionne sur des structures non triées
Elle s'arrête dès que l'élément est trouvé
Elle est simple à implémenter mais inefficace pour de grandes données

Meilleur cas

O(1)

Élément au début

Pire cas

O(n)

Élément à la fin

Moyenne

O(n)

Élément au milieu

\(\text{Comparaisons}_{\text{max}} = n\)

Nombre maximum de comparaisons

Points clés à retenir :

• La recherche linéaire est le moyen le plus simple de trouver un élément dans une structure
• Elle a une complexité linéaire O(n), ce qui la rend inefficace pour les grandes données
• Elle fonctionne sur des tableaux non triés, contrairement à la recherche dichotomique
• Elle s'arrête dès que l'élément est trouvé, ce qui optimise les cas favorables
• Elle est souvent utilisée pour des petites collections ou comme sous-routine dans d'autres algorithmes

Recherche linéaireExercices corrigés

Recherche linéaire
Exercices corrigés