Cours : Recherche Dichotomique (Itérative et Récursive)

1) Principe général

La recherche dichotomique (ou recherche binaire) applique le paradigme diviser pour régner : elle fonctionne uniquement sur un tableau trié. On commence avec une zone de recherche entière délimitée par deux bornes (début/gauche et fin/droite). À chaque étape, on calcule l’indice du milieu et on compare la clé avec l’élément central. Si l’élément central est égal à la clé, la recherche s’arrête immédiatement : la clé est trouvée. Si la clé est plus petite que l’élément central, alors toute la moitié droite est inutile (car le tableau est trié), on “règne” en la supprimant et on conserve seulement la moitié gauche. Sinon, si la clé est plus grande, on supprime la moitié gauche et on conserve la moitié droite. On répète exactement la même stratégie sur la sous-partie restante : c’est la phase “diviser” (réduire l’intervalle) puis “régner” (résoudre le sous-problème). La recherche se termine soit quand on trouve la clé, soit quand l’intervalle devient vide (début > fin), ce qui prouve que la clé n’existe pas dans le tableau. Cette méthode est rapide car à chaque comparaison, on divise la taille du problème par 2

La recherche dichotomique (ou recherche binaire) est une méthode rapide pour retrouver une valeur CLE dans un tableau trié (souvent en ordre croissant). Au lieu de parcourir toutes les cases, on compare la clé avec l’élément du milieu, puis on élimine la moitié inutile du tableau, et on recommence.

Indices utilisés

• g : borne gauche (début de la zone de recherche)
• d : borne droite (fin de la zone de recherche)
• m : milieu (middle) calculé par : m <- (g + d) DIV 2

Règle de décision

• Si T[m] = CLE : on a trouvé.
• Si CLE < T[m] : la clé est à gauche, donc d <- m - 1.
• Sinon : la clé est à droite, donc g <- m + 1.

La recherche s’arrête quand :

• la clé est trouvée, ou
• la zone de recherche devient vide : g > d (donc la clé est introuvable).

2) Exécutions manuelles (tableaux de trace)

2.1) Exemple sur un tableau de 10 éléments (N = 10)

On considère le tableau trié suivant (indices 1..10) :

T = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Cas A — La clé est en 1ère case (CLE = 2)

Cas B — La clé est en 2e case (CLE = 5)

Cas C — La clé est au milieu (CLE = 16)

Cas D — La clé n’existe pas (CLE = 10)

2.2) Exemple sur un tableau de 12 éléments (N = 12)

On considère le tableau trié suivant (indices 1..12) :

T = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36]

Cas E — Clé au début (CLE = 3)

Cas F — Clé au milieu (CLE = 21)

Cas G — Clé introuvable (CLE = 20)

3) Algorithme :

Attention : la recherche dichotomique nécessite un tableau trié. On lit donc d’abord les éléments, puis on applique un tri (ici Tri Sélection).

3.1) Algorithme itératif (ce n’est pas une fonction)

Algorithme RechercheDichotomique_Iterative ;
Const
    N = 20 ;
Var
    T : tableau[1..N] d'entier ;
    i : entier ;
    CLE : entier ;
    g, d, m : entier ;
    trouve : booleen ;

Debut
    /* 1) Lecture des éléments du tableau */
    Ecrire("Entrer ", N, " entiers :") ;
    Pour i de 1 a N Faire
        Lire(T[i]) ;
    FinPour

    /* 2) Tri du tableau avant la dichotomie */
    TriSelection(T) ;
    /* Remarque : on peut utiliser TriBulle(T) ou TriInsertion(T).
       Niveau 2 : TriRapide(T) ou TriFusion(T). */

    /* 3) Lecture de la clé à rechercher */
    Ecrire("Entrer la cle a rechercher : ") ;
    Lire(CLE) ;

    /* 4) Recherche dichotomique itérative */
    g <- 1 ;
    d <- N ;
    trouve <- FAUX ;

    Tantque (g <= d et trouve <> VRAI) Faire
        m <- (g + d) DIV 2 ;

        Si (T[m] = CLE) Alors
            trouve <- VRAI ;
        SinonSi (CLE < T[m]) Alors
            d <- m - 1 ;
        Sinon
            g <- m + 1 ;
        FinSi
    FinTantque

    /* 5) Affichage du résultat */
    Si (trouve = VRAI) Alors
        Ecrire("Cle trouvee a la position : ", m) ;
    Sinon
        Ecrire("Cle introuvable") ;
    FinSi
Fin.

3.2) Procédure Tri Sélection (pseudo-code)

Le tri sélection place à chaque passage le plus petit élément restant en tête de la zone non triée.

Procedure TriSelection(Var T : tableau[1..N] d'entier) ;
Var
    i, j, imin, tmp : entier ;
Debut
    Pour i de 1 a N-1 Faire
        imin <- i ;
        Pour j de i+1 a N Faire
            Si (T[j] < T[imin]) Alors
                imin <- j ;
            FinSi
        FinPour

        tmp <- T[i] ;
        T[i] <- T[imin] ;
        T[imin] <- tmp ;
    FinPour
Fin.

4) Version récursive (fonction) : dichotomie récursive

La version récursive renvoie directement la position de la clé (ou -1 si introuvable). Elle appelle la fonction sur la moitié gauche ou la moitié droite.

Fonction DichoRec(T : tableau[1..N] d'entier, debut, fin, CLE : entier) : entier ;
Var
    m : entier ;
Debut
    Si (debut > fin) Alors
        Retourner -1 ;
    FinSi

    m <- (debut + fin) DIV 2 ;

    Si (T[m] = CLE) Alors
        Retourner m ;
    SinonSi (CLE < T[m]) Alors
        Retourner DichoRec(T, debut, m - 1, CLE) ;
    Sinon
        Retourner DichoRec(T, m + 1, fin, CLE) ;
    FinSi
Fin.

Exemple d’appel (après tri)

pos <- DichoRec(T, 1, N, CLE) ;

Remarques (à retenir)

• La recherche dichotomique fonctionne seulement si le tableau est trié.
• À chaque étape, on réduit la zone de recherche à une moitié.
• Si la zone devient vide (g > d), alors la clé est introuvable.