🎯 Recherche Dichotomique : Cours & Principes

📖 1. Définition

La recherche dichotomique est un algorithme de recherche rapide hautement efficace qui s’applique exclusivement sur un tableau déjà trié, en divisant par deux l’espace de recherche à chaque itération.

⚙️ 2. Principe de l’algorithme

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

  • Définir deux bornes délimitant l’intervalle de recherche : une borne inférieure (deb ← 0) et une borne supérieure (fin ← n - 1).
  • Calculer l’indice du milieu de l’intervalle (milieu ← (deb + fin) Div 2).
  • Comparer la valeur recherchée x avec l’élément central T[milieu].
  • Si l’élément est trouvé, l’algorithme s’arrête ; sinon, on ajuste soit la borne deb, soit la borne fin selon que la cible est supérieure ou inférieure, et on répète tant que l’intervalle est valide.

⚠️ Note très importante :

L’utilisation de fonctions de recherche intégrées en Python (comme .index()) est strictement hors programme. Vous devez obligatoirement implémenter la logique des bornes itératives et de la division entière.

📊 Simulation Visuelle & Algorithme Animé

Recherche rapide par division successive de l’intervalle dans un tableau trié.

📊 Espace de simulation

🤖 m
deb ▲
fin ▲

Suivi de l’exécution :

deb Générez ou lancez la simulation…
m –
fin –
trouve Faux

Algorithme & TDOL :

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

TDOL

Objet Type
deb, fin, milieu Entier
trouve Booléen

💻 Traduction en Python

def recherche_dichotomique(t, n, x):
    deb = 0; fin = n - 1
    while deb <= fin:
        milieu = (deb + fin) // 2
        if t[milieu] == x:
            return milieu
        elif t[milieu] < x:
            deb = milieu + 1
        else:
            fin = milieu - 1
    return -1

📝 3. Exercice d'application

Situation : Dans une bibliothèque municipale, les codes d'identification des livres sont rigoureusement enregistrés dans l'ordre croissant sur un registre numérique. Pour retrouver rapidement la position d'un livre spécifique demandé par un abonné, le bibliothécaire applique la méthode de recherche par dichotomie.

Écrire un programme modulaire permettant de saisir un tableau trié de codes, de rechercher un code cible à l'aide d'une fonction dichotomique, et d'afficher son emplacement ou un message d'inexistence.

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

Correction détaillée

💻 Programme Principal (Algorithme)

Algorithme Recherche_Livre_Bibliotheque
DEBUT
  SaisieTaille(N)
  RemplirTableauTrie(Codes, N)
  Ecrire("Donner le code du livre recherché : ")
  Lire(Cible)
  Pos ← Recherche_Dichotomique(Codes, 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
Codes Tab
N, Cible, Pos Entier
SaisieTaille Procédure
RemplirTableauTrie Procédure
Recherche_Dichotomique 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 livres (entre 2 et 50) : ")
    Lire(n)
  Jusqu'à n dans [2..50]
FIN

TDOL : Aucun objet local.

2. Procédure RemplirTableauTrie

Procedure RemplirTableauTrie(@t: Tab, n: Entier)
DEBUT
  Ecrire("Saisie des codes par ordre croissant :")
  Pour i de 0 à n-1 Faire
    Répéter
      Ecrire("Code [", i, "] = ")
      Lire(t[i])
    Jusqu'à (i = 0) Ou (t[i] ≥ t[i-1])
  Fin Pour
FIN

TDOL : i (Entier)

3. Fonction Recherche_Dichotomique

Fonction Recherche_Dichotomique(t: Tab, n: Entier, x: Entier) : Entier
DEBUT
  deb ← 0
  fin ← n - 1
  trouve ← Faux
  Tant que (deb ≤ fin) Et (Non trouve) Faire
    milieu ← (deb + fin) Div 2
    Si t[milieu] = x Alors
      trouve ← Vrai
    Sinon
      Si t[milieu] < x Alors
        deb ← milieu + 1
      Sinon
        fin ← milieu - 1
      FinSi
    FinSi
  Fin Tant que
  Si trouve Alors
    Retourner milieu
  Sinon
    Retourner -1
  FinSi
FIN

TDOL : deb, fin, milieu (Entiers), trouve (Booléen)

4. Procédure AfficherResultat

Procedure AfficherResultat(p: Entier)
DEBUT
  Si p ≠ -1 Alors
    Ecrire("Livre trouvé à la position numéro : ", p)
  Sinon
    Ecrire("Désolé, le livre recherché n'existe pas dans le registre.")
  FinSi
FIN

TDOL : Aucun objet local.

🐍 Version Python (Traduction complète)

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

def remplir_tableau_trie(n):
    t = []
    print("Saisie des codes par ordre croissant :")
    for i in range(n):
        val = int(input(f"Code [{i}] = "))
        while i > 0 and val < t[i-1]:
            val = int(input(f"Erreur, doit être >= {t[i-1]}. Code [{i}] = "))
        t.append(val)
    return t

def recherche_dichotomique(t, n, x):
    deb = 0; fin = n - 1
    while deb <= fin:
        milieu = (deb + fin) // 2
        if t[milieu] == x:
            return milieu
        elif t[milieu] < x:
            deb = milieu + 1
        else:
            fin = milieu - 1
    return -1

def afficher_resultat(p):
    if p != -1:
        print("Livre trouvé à la position numéro :", p)
    else:
        print("Désolé, le livre recherché n'existe pas dans le registre.")

# Programme Principal
N = saisie_taille()
Codes = remplir_tableau_trie(N)
Cible = int(input("Donner le code du livre recherché : "))
Pos = recherche_dichotomique(Codes, N, Cible)
afficher_resultat(Pos)