🔍 Recherche Séquentielle : Cours & Principes

📖 1. Définition

La recherche séquentielle (ou linéaire) est l’algorithme de recherche le plus simple qui consiste à inspecter les éléments d’un tableau un par un, dans l’ordre, jusqu’à trouver la valeur cible ou atteindre la fin du tableau.

⚙️ 2. Principe de l’algorithme

Le fonctionnement repose sur les étapes clés suivantes :

  • Initialiser un indice de parcours (i ← 0) et un indicateur booléen de succès (trouve ← Faux).
  • Parcourir le tableau tant que la fin n’est pas atteinte et que l’élément n’a pas encore été trouvé.
  • Tester si l’élément courant T[i] correspond à la valeur recherchée x.
  • Si c’est le cas, positionner trouve ← Vrai ; sinon, passer à l’élément suivant (i ← i + 1).

⚠️ Note très importante :

L’utilisation de fonctions intégrées en Python comme .index() ou l’opérateur in direct est strictement hors programme. Vous devez obligatoirement implémenter la logique itérative du parcours séquentiel avec un drapeau ou une condition d’arrêt.

📊 Simulation Visuelle & Algorithme Animé

Parcours élément par élément du tableau jusqu’à trouver la valeur cible.

📊 Espace de simulation

🤖 i

Suivi de l’exécution :

i Générez ou lancez la simulation…
trouve Faux

Algorithme & TDOL :

Fonction Recherche_Sequentielle(T: Tab, n: Entier, x: Entier) : Entier
Début
    i ← 0
    trouve ← Faux
    Tant que (i < n) Et (Non trouve) Faire
        Si T[i] = x Alors
            trouve ← Vrai
        Sinon
            i ← i + 1
        FinSi
    FinTantQue
    Si trouve Alors Retourner i Sinon Retourner -1 FinSi
Fin.

TDOL

Objet Type
i Entier
trouve Booléen

💻 Traduction en Python

def recherche_sequentielle(t, n, x):
    i = 0
    trouve = False
    while i < n and not trouve:
        if t[i] == x:
            trouve = True
        else:
            i += 1
    return i if trouve else -1

📝 3. Exercice d'application

Situation : Dans une agence de voyage, les numéros de passeport des clients inscrits pour un vol charter sont enregistrés dans une liste non triée. Pour vérifier rapidement si un client spécifique fait partie du voyage, l'agent utilise une recherche séquentielle.

Écrire un programme modulaire permettant de saisir les numéros de passeport, de rechercher un numéro cible à l'aide d'une fonction séquentielle, et d'afficher le résultat de la vérification.

Donner la solution sous forme d'algorithme et sa traduction en programme Python.

Correction détaillée

💻 Programme Principal (Algorithme)

Algorithme Verification_Passeport_Voyage
DEBUT
  SaisieTaille(N)
  RemplirTableau(Passeports, N)
  Ecrire("Donner le numéro de passeport recherché : ")
  Lire(Cible)
  Pos ← Recherche_Sequentielle(Passeports, N, Cible)
  AfficherResultat(Pos)
FIN

📋 Tableaux de Déclaration (TDNT & TDOG)

TDNT

Type Structure
Tab Tableau de 50 entiers

TDOG (avec les noms des modules)

Objet Type / Nature
Passeports Tab
N, Cible, Pos Entier
SaisieTaille Procédure
RemplirTableau Procédure
Recherche_Sequentielle Fonction
AfficherResultat Procédure

⚙️ Liste des Modules et TDOL

1. Procédure SaisieTaille

Procedure SaisieTaille(@n: Entier)
DEBUT
  Répéter
    Ecrire("Donner le nombre de passagers (entre 2 et 50) : ")
    Lire(n)
  Jusqu'à n dans [2..50]
FIN

TDOL : Aucun objet local.

2. Procédure RemplirTableau

Procedure RemplirTableau(@t: Tab, n: Entier)
DEBUT
  Pour i de 0 à n-1 Faire
    Ecrire("Passeport [", i, "] = ")
    Lire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

3. Fonction Recherche_Sequentielle

Fonction Recherche_Sequentielle(t: Tab, n: Entier, x: Entier) : Entier
DEBUT
  i ← 0
  trouve ← Faux
  Tant que (i < n) Et (Non trouve) Faire
    Si t[i] = x Alors
      trouve ← Vrai
    Sinon
      i ← i + 1
    FinSi
  Fin Tant que
  Si trouve Alors
    Retourner i
  Sinon
    Retourner -1
  FinSi
FIN

TDOL : i (Entier), trouve (Booléen)

4. Procédure AfficherResultat

Procedure AfficherResultat(p: Entier)
DEBUT
  Si p ≠ -1 Alors
    Ecrire("Client enregistré ! Position sur la liste : ", p)
  Sinon
    Ecrire("Client introuvable sur la liste des passagers.")
  FinSi
FIN

TDOL : Aucun objet local.

🐍 Version Python (Traduction complète)

def saisie_taille():
    n = int(input("Nombre de passagers (2-50) : "))
    while not (2 <= n <= 50):
        n = int(input("Erreur (2-50) : "))
    return n

def remplir_tableau(n):
    return [int(input(f"Passeport [{i}] = ")) for i in range(n)]

def recherche_sequentielle(t, n, x):
    i = 0
    trouve = False
    while i < n and not trouve:
        if t[i] == x:
            trouve = True
        else:
            i += 1
    return i if trouve else -1

def afficher_resultat(p):
    if p != -1:
        print("Client enregistré ! Position sur la liste :", p)
    else:
        print("Client introuvable sur la liste des passagers.")

# Programme Principal
N = saisie_taille()
Passeports = remplir_tableau(N)
Cible = int(input("Donner le numéro de passeport recherché : "))
Pos = recherche_sequentielle(Passeports, N, Cible)
afficher_resultat(Pos)