Recherche dichotomique.

Soit un vecteur A de dimension N dans lequel nous devons rechercher la position d'un élément y apparaissant éventuellment.
La méthode la plus rudimentaire consiste à passer tous les éléments du tableau en revue en commençant par le premier et en s'arrêtant lorsque l'élément est trouvé ou lorsque le dernier élément est atteint: il s'agit d'une recherche séquentielle.
Ce type de recherche impose un nombre de tests compris entre 1 (si l'élément recherché est en 1ère position) et N (si l'élément recherché est en dernière position), pour une moyenne de (1+2+...+N)/N = [(1+N)N/2]/N = (1+N)/2 tests.

Lorsque l'information contenue dans le tableau n'est pas triée ou triée suivant un critère qu'il n'est pas possible d'exploiter, cette recherche est la seule possible mais si le tableau est trié sur un critère exploitable, nous allons pouvoir diminuer notablement le nombre d'opérations à effectuer par une recherche dichotomique.

Imaginons que nous devions trouver le nombre 4 dans le tableau trié ci-dessous:

Si nous comparons le nombre à chercher à l'élément (en rouge) se trouvant au milieu du tableau (dont les extrémités sont marquées par un élément en jaune et un élément en mauve), nous constatons qu'il doit se trouver (s'il est dans le tableau) dans la partie se trouvant devant l'élément en rouge. Et nous pouvons même préciser qu'il doit se trouver entre les positions 1 (marquée en jaune) et 5 (qui sera marquée en mauve) (puisqu'il n'est pas en position 6).

Si nous comparons le nombre à chercher à l'élément se trouvant au milieu de la partie du tableau dont les limites sont indiquées par les nombres en jaune et mauve, nous constatons qu'il doit se trouver (s'il est dans le tableau) dans la 2ème partie (celle se trouvant après l'élément en rouge). Et nous pouvons même préciser qu'il doit se trouver entre les positions 4 (qui sera marquée en jaune) (puisqu'il n'est pas en position 3) et 5 (marquée en mauve).

Si nous comparons le nombre à chercher à l'élément (en rouge) se trouvant au milieu de la partie du tableau dont les limites sont indiquées par les nombres en jaune et mauve, nous constatons qu'il doit se trouver (s'il est dans le tableau) dans la 1ère partie (celle se trouvant avant l'élément en rouge). Et nous pouvons même préciser qu'il doit se trouver entre les positions 3 (marquée en jaune) et 3 (puisqu'il n'est pas en position 4) (qui sera marquée en mauve).

Si nous comparons le nombre à chercher à l'élément (en rouge) se trouvant au milieu de la partie du tableau dont les limites sont indiquées par les nombres en jaune et mauve, nous constatons qu'il ne s'y trouve pas et que nous sommes arrivés à la conclusion que 4 ne se trouve pas dans le tableau.

Nous pouvons constater qu'à la première étape, nous devions prendre le milieur d'un tableau de N éléments, à l'étape suivante le milieu d'un tableau de N/2 éléments, puis de N/4 éléments, ...
Dans le plus mauvais des cas, la recherche s'arrête quand le nombre d'éléments est réduit à 1 et donc quand N/2^k<=1 ou quand N<=2^k c'est-à-dire quand k est le plus petit entier>=log₂N.
Pour 1024 éléments, nous nous en tirerons donc avec un maximum de 10 étapes, à rapprocher des 1024 étapes de la recherche séquentielle!

Voici l'algorithme en pseudo-code. Il comprend une 2ème partie pour rechercher si l'élément cherché apparaît plusieurs fois. Il serait plus intéressant de recommencer une recherche dichotomique pour trouver ces éléments mais dans un but pédagogique, je demande à mes étudiants d'appliquer une recherche séquentielle et ceci est donc la version que je leur demande.

Type Tabl = tableau_i i=1,...,1000 de entier
fonction CréeTabTrié(N)
  paramètre N: entier  
  à valeur Tabl
Tabl: T
T₁ ß RANDOM(3)
pour i de 2 à N faire  
  T_i ß T_i-1 + RANDOM(3)
fpour
résultat (T)

fonction Hasard(Min, Max)
  paramètres: Min, Max: entier
  à valeur: entier
entier: tmp
tmp ß Min+RANDOM(Max-Min+1)
résultat (tmp)

fonction Cherche(X, N, T)
  paramètres: X, N: entier
              T: Tabl
  à valeur: entier
entier: Min, Max, c, Tmp
Min ß 1
Max ß N
c ß (Min+Max)\2
tant que NOT ((Max-Min£ 1) ou (X=T_c)) faire
  si X<T_c alors Max ß c
  sinon Min ß c
  fsi
  c ß (Min+Max)\2
ftant
si X=T_c alors Tmp ß c
sinon Tmp ß 0
fsi
résultat (Tmp)

entier: N, X, P
Tabl: Tab
N ß 100
Tab ß CréeTabTrié(N)
X ß Hasard(Tab₁ ,Tab_N)
écrire X
P ß Cherche(X, N, Tab)
si P=0 alors écrire X,"n'a pas été trouvé dans le tableau"
sinon écrire X,"a été trouvé en position", P, "dans le tableau"
fsi

ou si on cherche toutes les positions de X séquentiellement:

procédure ChercheTous(¯ X, ¯ N, ¯ T,  Inf,  Sup)
  paramètres: X, N; Inf, Sup: entier
  T: Tabl
entier: Min, Max, c, i
Min ß 1
Max ß N
c ß (Min+Max)\2
tant que NOT ((Max-Min£ 1) ou (X=T_c)) faire
  si X<T_c alors Max ß c-1
  sinon Min ß c+1
  fsi
  c ß (Min+Max)\2
ftant
si X=T_c alors i ß c
              tant que NOT ((X¹ T_i) ou (i=Min)) faire
                i ß i-1
              ftant
              si X¹ T_i alors Inf ß i+1
              sinon Inf ß i
              fsi
              i ß c
              tant que NOT ((X¹ T_i) ou (i=Max)) faire
                i ß i+1
              ftant
              si X¹ T_i alors Sup ß i-1
              sinon Sup ß i
              fsi
sinon Min ß 0
Max ß 0
fsi
fproc

Cliquez ici pour charger le source et l'exécutable en Delphi.
Dans cette version, la recherche se fait dans une liste de nombres que vous devez encoder dans un Memo.

Page d'accueil.