Recherche séquentielle et dichotomique

Avant de commencer

Vous cherchez un mot dans un dictionnaire. Naturellement, vous n'ouvrez pas page 1 pour parcourir page par page — vous ouvrez au milieu, vous voyez si le mot est avant ou après, et vous coupez la moitié restante en deux. C'est la recherche dichotomique.

1. Recherche séquentielle

DEF FN RechSeq(T : Tab, n : entier, val : entier) : entier
  i ← 1
  Tant que (i <= n) ET (T[i] ≠ val) Faire
    i ← i + 1
  FinTantQue
  Si i > n Alors
    RechSeq ← -1    { non trouvé }
  Sinon
    RechSeq ← i     { position trouvée }
  FinSi
Fin RechSeq

FUNCTION RechSeq(T : Tab; n, val : integer) : integer;
VAR
  i : integer;
BEGIN
  i := 1;
  WHILE (i <= n) AND (T[i] <> val) DO
    i := i + 1;
  IF i > n THEN
    RechSeq := -1
  ELSE
    RechSeq := i;
END;

Complexité : pire cas O(n) (val à la fin ou absente).

2. Recherche dichotomique

DEF FN RechDicho(T : Tab, n : entier, val : entier) : entier
  inf ← 1
  sup ← n
  trouve ← Faux
  Tant que (inf <= sup) ET (NON trouve) Faire
    milieu ← (inf + sup) div 2
    Si T[milieu] = val Alors
      trouve ← Vrai
    Sinon Si val < T[milieu] Alors
      sup ← milieu - 1
    Sinon
      inf ← milieu + 1
    FinSi
  FinTantQue
  Si trouve Alors
    RechDicho ← milieu
  Sinon
    RechDicho ← -1
  FinSi
Fin RechDicho

FUNCTION RechDicho(T : Tab; n, val : integer) : integer;
VAR
  inf, sup, milieu : integer;
  trouve : boolean;
BEGIN
  inf := 1; sup := n;
  trouve := false;
  milieu := 0;
  WHILE (inf <= sup) AND NOT trouve DO
  BEGIN
    milieu := (inf + sup) DIV 2;
    IF T[milieu] = val THEN
      trouve := true
    ELSE IF val < T[milieu] THEN
      sup := milieu - 1
    ELSE
      inf := milieu + 1;
  END;
  IF trouve THEN
    RechDicho := milieu
  ELSE
    RechDicho := -1;
END;

3. Pourquoi la dichotomie est-elle si rapide ?

À chaque étape, on divise par 2 la taille du segment à fouiller. Au bout de k étapes, il reste n / 2^k éléments.

On s'arrête quand n / 2^k = 1, soit k = log₂(n).

4. Trace d'exécution dichotomique

Sur T = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (n=10), on cherche 23.

5. Exercices

FUNCTION Compter(T : Tab; n, val : integer) : integer;
VAR
  i, cpt : integer;
BEGIN
  cpt := 0;
  FOR i := 1 TO n DO
    IF T[i] = val THEN
      cpt := cpt + 1;
  Compter := cpt;
END;

PROCEDURE Inserer(VAR T : Tab; VAR n : integer; val : integer);
VAR
  inf, sup, milieu, i : integer;
BEGIN
  { Recherche dichotomique de la position d'insertion }
  inf := 1; sup := n;
  WHILE inf <= sup DO
  BEGIN
    milieu := (inf + sup) DIV 2;
    IF val < T[milieu] THEN
      sup := milieu - 1
    ELSE
      inf := milieu + 1;
  END;
  { À la sortie, inf est la position d'insertion }

  { Décalage }
  FOR i := n DOWNTO inf DO
    T[i + 1] := T[i];

  T[inf] := val;
  n := n + 1;
END;

6. Erreurs fréquentes au bac

• Utiliser la dichotomie sur un tableau non trié → résultat erroné.
• Oublier inf ← milieu + 1 (ou sup ← milieu - 1) : sans +1/−1, on peut boucler infiniment.
• Confondre inf et sup au moment du milieu : (inf + sup) div 2.
• Renvoyer milieu même quand trouve = Faux : il faut tester avant.

7. Quiz