Le principe de dichotomie

Important

Ce principe de dichotomie est à connaître parfaitement.

Le principe

On recherche la présence d'un élément dans un tableau trié en ordre croissant.

Illustrons le principe avec un exemple.
On cherche si 8 est présent dans le tableau, trié en ordre croissant, tab = [2, 4, 7, 9, 12, 15, 17, 23].

• On commence par tester un élément en "milieu" de tableau ([2, 4, 7, 9, 12, 15, 17, 23]):
  9 n'est pas égal à 8.

• Comme le tableau est trié et que 8 < 9, si 8 est présent ce ne peut être qu'à gauche de 9.
  Au lieu de chercher dans tout le tableau, on peut donc maintenant réduire la recherche à la partie à gauche de 9: [2, 4, 7].

• On procède comme précédemment: on teste une valeur "en milieu" de tableau ([2, 4, 7]). 4 n'est pas égal à 8, donc on poursuit la recherche.

• Comme 8 > 4, si 8 est présent ce ne peut être qu'à droite de 4. On peut donc limiter la recherche au sous-tableau de droite de 4: [7].

• On compare enfin 8 à l'unique valeur restante: 7 n'est pas égal à 8, donc 8 est absent du tableau.

milieu entier

Le milieu de l'intervalle [a; b] est $\frac{a+b}{2}$. Ici, notre "milieu" doit rester entier. On définira le "milieu entier" de [a; b] (où a et b sont entiers) par m = (a+b)//2 (c'est à dire: m est le quotient de la division entière de a+b par 2).

Ainsi le milieu entier de [1; 12] est (1+12)//2 = 6.