Principe de la recherche dichotomique

Problématique

Cette recherche de présence d'un élément s'effectue dans un tableau trié (par ordre croissant).

La méthode

1. Si le tableau est vide, la recherche est terminé : l'élément n'appartient pas au tableau.
2. Si le tableau n'est pas vide, on compare l'élément à la valeur la plus centrale du tableau :
   1. ou bien la valeur est celle recherchée : c'est terminé.
   2. ou bien la valeur est plus petite que l'élément recherché alors on recommence la procédure avec la seconde moitié du tableau.
   3. ou bien la valeur est plus grande que l'élément recherché alors on recommence la procédure avec la première moitié du tableau.

Problème du « milieu »

En mathématiques, le milieu (ou centre) de l'intervalle $[a ; b]$ est $\frac{a+b}{2}$.

Dans le raisonnement précédent, c'est l'indice du milieu que l'on cherche et cet indice doit être, par définition, un entier. Or le milieu entre les nombres $5$ et $8$ n'est pas entier : $\frac{5+8}{2} = 6,5$.

Pour éviter de choisir entre $6$ et $7$, on prendra la convention suivante :
Le « milieu entier » entre les entiers $a$ et $b$ est la partie entière de $\frac{a+b}{2}$.

En Python, le « milieu entier » de [a ; b] (où a et b sont entiers) sera ainsi m = (a+b)//2 (c'est-à-dire le quotient de la division entière de a+b par 2).

Illustration

On va utiliser ce raisonnement pour vérifier si la valeur 8 est présente dans le tableau :

tab =

2

4

7

9

10

12

15

17

23

• On considère au départ l'ensemble du tableau :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

  Les indices vont de $0$ à $8$, l'indice du milieu est la partie entière de $\frac{0+8}{2}$, c'est-à-dire $4$ :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

• Puisque $10 > 8$, on recommence la procédure dans la première partie du tableau :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

  Les indices vont de $0$ à $3$, l'indice du milieu est la partie entière de $\frac{0+3}{2}$, c'est-à-dire $1$ :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

• Puisque $4 < 8$, on recommence la procédure dans la deuxième partie colorée :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

  Les indices vont de $2$ à $3$, l'indice du milieu est la partie entière de $\frac{2+3}{2}$, c'est-à-dire $2$ :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

• Puisque $7 < 8$, on recommence la procédure dans la deuxième partie colorée qui ne contient qu'un seul élément :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

  Les indices vont de $3$ à $3$, l'indice du milieu est la partie entière de $\frac{3+3}{2}$, c'est-à-dire $3$ :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

• Puisque $9 > 8$, la recherche s'arrête là car le tableau (orange) dans lequel on recherche est vide :

  tab =

  2

  4

  7

  9

  10

  12

  15

  17

  23

On peut conclure en quatre étapes que 8 est absent de ce tableau.

Vocabulaire

Le mot dichotomie provient du grec ancien et signifie « couper en deux ».