La recherche dichotomique

Recherche

Chercher dans un tableau TRIÉ en coupant l’intervalle en deux à chaque tour.

Ce qui se passe, dans l’ordre

Le tableau DOIT être trié : c’est ce qui permet d’éliminer une moitié d’un coup.

On regarde la case du milieu, puis on ne garde que la moitié qui peut contenir la valeur.

Sept cases se règlent en trois comparaisons au lieu de sept.

L’erreur qui coûte les points

Sur un tableau non trié, la dichotomie répond « absent » alors que la valeur y est.

Ce que l’épreuve en demande

Le jury fait plus souvent tracer un algorithme que l’écrire : on te donne le code et des valeurs, tu déroules à la main. Exécute ici, puis compare avec ce que tu avais écrit.

Et n’oublie pas la table : tout livrable algorithmique exige son T.D.O. L’onglet à côté du code ne te la donne pas — c’est à toi de l’écrire, objet par objet, puis de la faire vérifier. C’est le geste exact du jour J, et un algorithme juste sans sa table perd quand même des points.

123456789101112131415161718192021222324252627282930313233343536

Algorithme Dichotomie
Variables
  T : Tableau de 7 Entiers
  inf, sup, mil, val : Entier
  trouve : Booléen
Début
  T[0] ← 2
  T[1] ← 5
  T[2] ← 8
  T[3] ← 12
  T[4] ← 16
  T[5] ← 23
  T[6] ← 38
  val ← 23
  inf ← 0
  sup ← 6
  trouve ← Faux
  Tant Que (inf <= sup) Et (trouve = Faux) Faire
    mil ← (inf + sup) Div 2
    Ecrire("on regarde T[", mil, "] = ", T[mil])
    Si T[mil] = val Alors
      trouve ← Vrai
    Sinon
      Si T[mil] < val Alors
        inf ← mil + 1
      Sinon
        sup ← mil - 1
      Fin Si
    Fin Si
  Fin Tant Que
  Si trouve = Vrai Alors
    Ecrire(val, " trouvé à l'indice ", mil)
  Sinon
    Ecrire(val, " absent")
  Fin Si
Fin

Ctrl + Entrée

La recherche dichotomique

Recherche

Chercher dans un tableau TRIÉ en coupant l’intervalle en deux à chaque tour.

Ce qui se passe, dans l’ordre

Le tableau DOIT être trié : c’est ce qui permet d’éliminer une moitié d’un coup.

On regarde la case du milieu, puis on ne garde que la moitié qui peut contenir la valeur.

Sept cases se règlent en trois comparaisons au lieu de sept.

L’erreur qui coûte les points

Sur un tableau non trié, la dichotomie répond « absent » alors que la valeur y est.

Ce que l’épreuve en demande

Le jury fait plus souvent tracer un algorithme que l’écrire : on te donne le code et des valeurs, tu déroules à la main. Exécute ici, puis compare avec ce que tu avais écrit.

Algorithme Dichotomie Variables T : Tableau de 7 Entiers inf, sup, mil, val : Entier trouve : Booléen Début T[0] ← 2 T[1] ← 5 T[2] ← 8 T[3] ← 12 T[4] ← 16 T[5] ← 23 T[6] ← 38 val ← 23 inf ← 0 sup ← 6 trouve ← Faux Tant Que (inf <= sup) Et (trouve = Faux) Faire mil ← (inf + sup) Div 2 Ecrire("on regarde T[", mil, "] = ", T[mil]) Si T[mil] = val Alors trouve ← Vrai Sinon Si T[mil] < val Alors inf ← mil + 1 Sinon sup ← mil - 1 Fin Si Fin Si Fin Tant Que Si trouve = Vrai Alors Ecrire(val, " trouvé à l'indice ", mil) Sinon Ecrire(val, " absent") Fin Si Fin