Voici le détail des algorithmes de recherche avec des explications pas à pas, suivis de deux exemples d’exécution pour chaque méthode, et enfin la correction des travaux dirigés.

---

I. Recherche séquentielle linéaire

Explication détaillée du code

Cette méthode consiste à parcourir le tableau élément par élément en partant du début (indice 1). On compare chaque élément V[i] avec la valeur recherchée val.

• La boucle Tant que continue tant qu’on n’a pas atteint la fin du tableau (i <= n) ET tant que la valeur actuelle n’est pas celle recherchée (val ≠ V[i]).
• À la sortie de la boucle, il y a deux cas : soit on a trouvé la valeur, soit on est arrivé à la fin du tableau sans trouver.
• Le test si val = V[i] permet de distinguer ces deux cas.

Code détaillé avec points-virgules

Fonction recherche_sequentielle(V: vecteur, n: entier, val: entier, Var pos: entier): booléen;
Var i: entier;
Début
    i ← 1; // Initialisation de l'indice de parcours

    // Parcours du tableau jusqu'à trouver la valeur ou arriver à la fin
    Tant que (i <= n) et (val ≠ V[i]) faire
        i ← i + 1; // On passe à l'élément suivant
    Fin Tant que;

    // Après la boucle, on vérifie si on s'est arrêté parce qu'on a trouvé
    Si val = V[i] alors
        recherche_sequentielle ← Vrai; // On retourne Vrai
        pos ← i;                       // On sauvegarde la position trouvée
    Sinon
        recherche_sequentielle ← Faux; // On retourne Faux (non trouvé)
        pos ← 0;                       // Position invalide par convention
    Fin Si;
Fin;

Exemples d’exécution

Soit le tableau V = [10, 50, 30, 20, 40] (taille n = 5).

Exemple 1 : Recherche de la valeur 30

1. i = 1. V[1] (10) ≠ 30. On continue. i devient 2.
2. i = 2. V[2] (50) ≠ 30. On continue. i devient 3.
3. i = 3. V[3] (30) = 30. La condition val ≠ V[i] est fausse. La boucle s’arrête.
4. Test Si val = V[i] (30 = 30) est Vrai.
5. Résultat : Fonction retourne Vrai, pos = 3.

Exemple 2 : Recherche de la valeur 60

1. i = 1. V[1] (10) ≠ 60. i devient 2.
2. i = 2. V[2] (50) ≠ 60. i devient 3.
3. i = 3. V[3] (30) ≠ 60. i devient 4.
4. i = 4. V[4] (20) ≠ 60. i devient 5.
5. i = 5. V[5] (40) ≠ 60. i devient 6.
6. Boucle s’arrête car i (6) > n (5).
7. Test Si val = V[i] (60 = V[6] ?). V[6] n’existe pas ou est indéfini, mais logiquement la condition est fausse.
8. Résultat : Fonction retourne Faux.

---

II. Recherche séquentielle avec sentinelle

Explication détaillée du code

L’idée est d’éviter de vérifier à chaque itération si on a dépassé la taille du tableau (i <= n). Pour cela, on place la valeur recherchée val à la fin du tableau (case n+1), qu’on appelle “sentinelle”.

• On est ainsi garanti que la boucle finira par trouver la valeur (au pire à la position n+1).
• Après la boucle, il suffit de tester si l’indice i est inférieur ou égal à n. Si oui, c’est une vraie trouvaille. Si non (i = n+1), c’était la sentinelle (donc absent du tableau original).

Code détaillé avec points-virgules

Note : Le tableau V doit être déclaré avec une taille physique de n+1.

Fonction recherche_sequentielle_sentinelle(Var V: vecteur, N: entier, val: entier, Var pos: entier): booléen;
Var i: entier;
Début
    i ← 1;             // Initialisation
    V[N+1] ← val;      // Placement de la sentinelle à la fin

    // On cherche sans se soucier des bornes (la sentinelle arrêtera la boucle)
    Tant que val ≠ V[i] faire
        i ← i + 1;
    Fin Tant que;

    // On vérifie si l'arrêt s'est fait avant la sentinelle
    Si i <= N alors
        recherche_sequentielle_sentinelle ← Vrai;
        pos ← i;
    Sinon
        recherche_sequentielle_sentinelle ← Faux;
        pos ← 0;
    Fin Si;
Fin;

Exemples d’exécution

Soit le tableau V (taille physique 6, taille logique N = 5). V = [10, 50, 30, 20, 40, ?].

Exemple 1 : Recherche de la valeur 20

1. On place la sentinelle : V[6] ← 20. Le tableau est [10, 50, 30, 20, 40, 20].
2. i = 1. V[1] (10) ≠ 20. i ← 2.
3. i = 2. V[2] (50) ≠ 20. i ← 3.
4. i = 3. V[3] (30) ≠ 20. i ← 4.
5. i = 4. V[4] (20) = 20. La boucle s’arrête.
6. Test Si i <= N (4 <= 5) est Vrai.
7. Résultat : Fonction retourne Vrai, pos = 4.

Exemple 2 : Recherche de la valeur 100

1. On place la sentinelle : V[6] ← 100. Le tableau est [10, 50, 30, 20, 40, 100].
2. Parcours complet : i va de 1 à 5 sans trouver 100.
3. i = 6. V[6] (100) = 100. La boucle s’arrête.
4. Test Si i <= N (6 <= 5) est Faux.
5. Résultat : Fonction retourne Faux (la valeur était la sentinelle, donc absente).

---

III. Recherche dichotomique

Explication détaillée du code

Cette méthode est beaucoup plus rapide mais nécessite que le tableau soit trié.

• On délimite une zone de recherche entre min (début) et max (fin).
• On calcule le milieu mil.
• On compare la valeur cherchée avec V[mil].
  • Si V[mil] est la valeur, c’est gagné.
  • Si val est plus petite, on sait qu’elle se trouve dans la moitié gauche. On déplace max avant mil.
  • Si val est plus grande, on sait qu’elle se trouve dans la moitié droite. On déplace min après mil.
• On répète jusqu’à trouver ou jusqu’à ce que la zone soit vide (min > max).

Code détaillé avec points-virgules

Fonction rech(V: vecteur, n: entier, val: entier, Var pos: entier): booléen;
Var mil, min, max: entier;
Var trouve: booléen;
Début
    min ← 1;
    max ← n;
    trouve ← Faux;

    // Tant que la zone de recherche est valide et qu'on n'a pas trouvé
    Tant que (min <= max) et (non trouve) faire
        mil ← (min + max) div 2; // Calcul de l'indice milieu (division entière)

        Si val < V[mil] alors
            max ← mil - 1; // On ignore la moitié droite
        Sinon
            Si val > V[mil] alors
                min ← mil + 1; // On ignore la moitié gauche
            Sinon
                trouve ← Vrai; // val = V[mil], on a trouvé
            Fin Si;
        Fin Si;
    Fin Tant que;

    Si trouve alors
        pos ← mil;
    Sinon
        pos ← 0;
    Fin Si;

    rech ← trouve;
Fin;

Exemples d’exécution

Soit le tableau V trié : [5, 12, 20, 35, 42, 58] (taille n = 6).

Exemple 1 : Recherche de la valeur 12

1. Départ : min = 1, max = 6. mil = (1+6) div 2 = 3. V[3] = 20. Comparaison : 12 < 20. Action : On va à gauche. max devient mil - 1 = 2.
2. Nouvelle zone : min = 1, max = 2. mil = (1+2) div 2 = 1. V[1] = 5. Comparaison : 12 > 5. Action : On va à droite. min devient mil + 1 = 2.
3. Nouvelle zone : min = 2, max = 2. mil = (2+2) div 2 = 2. V[2] = 12. Comparaison : 12 = 12. Action : trouve ← Vrai.
4. Résultat : Fonction retourne Vrai, pos = 2.

Exemple 2 : Recherche de la valeur 15

1. Départ : min = 1, max = 6. mil = 3. V[3] = 20. Comparaison : 15 < 20. Action : max ← 2.
2. Zone : min = 1, max = 2. mil = 1. V[1] = 5. Comparaison : 15 > 5. Action : min ← 2.
3. Zone : min = 2, max = 2. mil = 2. V[2] = 12. Comparaison : 15 > 12. Action : min ← 3.
4. Test boucle : min (3) > max (2). La boucle s’arrête.
5. Résultat : Fonction retourne Faux.

---

IV. Travaux dirigés (Corrigé)

Exercice 1 : Analyse de l’algorithme

L’algorithme mentionné utilise une boucle Pour i de 1 à n. Cela signifie que même si la valeur est trouvée au premier indice, la boucle continue de parcourir tout le tableau jusqu’au bout. Inconvénient : C’est une perte de temps (complexité linéaire obligatoire O(n) même dans le meilleur des cas). Amélioration : Utiliser une boucle Tant que (comme vu dans le cours) permet de s’arrêter dès que l’élément est trouvé, ce qui optimise le temps d’exécution.

Exercice 2 : Plus petit élément et position

Procédure TrouverMin();
Var T : tableau[1..100] de réel;
Var i, pos_min : entier;
Var min_val : réel;
Début
    // Saisie des 100 réels
    Pour i ← 1 à 100 faire
        Ecrire("Entrez un réel : ");
        Lire(T[i]);
    Fin Pour;

    // Initialisation avec le premier élément
    min_val ← T[1];
    pos_min ← 1;

    // Parcours pour trouver le minimum
    Pour i ← 2 à 100 faire
        Si T[i] < min_val alors
            min_val ← T[i];
            pos_min ← i;
        Fin Si;
    Fin Pour;

    Ecrire("La valeur minimale est : ", min_val);
    Ecrire("Elle se trouve à la position : ", pos_min);
Fin;

Exercice 3 : Procédures et Fonction combinées

1. Procédure de saisie

Procédure SaisirTab(Var T : tableau de réel, n : entier);
Var i : entier;
Début
    Pour i ← 1 à n faire
        Ecrire("Entrez l'élément ", i, " : ");
        Lire(T[i]);
    Fin Pour;
Fin;

2. Procédure de tri (Tri à bulles)

Procédure TriTab(Var T : tableau de réel, n : entier);
Var i, j : entier;
Var temp : réel;
Début
    Pour i ← 1 à n-1 faire
        Pour j ← 1 à n-i faire
            Si T[j] > T[j+1] alors
                temp ← T[j];
                T[j] ← T[j+1];
                T[j+1] ← temp;
            Fin Si;
        Fin Pour;
    Fin Pour;
Fin;

3. Fonction de recherche dichotomique

Fonction RechercheDicho(T : tableau de réel, n : entier, val : réel) : booléen;
Var min, max, mil : entier;
Var trouve : booléen;
Début
    min ← 1;
    max ← n;
    trouve ← Faux;

    Tant que (min <= max) et (non trouve) faire
        mil ← (min + max) div 2;
        Si T[mil] = val alors
            trouve ← Vrai;
        Sinon
            Si val < T[mil] alors
                max ← mil - 1;
            Sinon
                min ← mil + 1;
            Fin Si;
        Fin Si;
    Fin Tant que;

    RechercheDicho ← trouve;
Fin;