pdf présentation et slides

Recherche dichotomique dans un tableau

Contexte

• Un tableau trié : T = [0, 1, 2, ... ,9]

• L’élément 3 est-il dans le tableau ?

• L’objectif : répondre Oui ou Non en réalisant le moins d’opérations possibles.

Dichotomie

• À chaque étape on teste la valeur centrale
• Si c’est l’élément cherché, on a trouvé et la réponse est Oui.

Dichotomie

• À chaque étape on teste la valeur centrale
• Si c’est l’élément cherché, on a trouvé et la réponse est Oui.
• Si la valeur centrale est supérieure à l’élément cherché on recommence avec la partie gauche

Dichotomie

• À chaque étape on teste la valeur centrale
• Si c’est l’élément cherché, on a trouvé et la réponse est Oui.
• Si la valeur centrale est supérieure à l’élément cherché on recommence avec la partie gauche
• Sinon on recommence avec la partie droite.

Dichotomie

• À chaque étape on teste la valeur centrale
• Si c’est l’élément cherché, on a trouvé et la réponse est Oui.
• Si la valeur centrale est supérieure à l’élément cherché on recommence avec la partie gauche
• Sinon on recommence avec la partie droite.
• Si la partie gauche ou la partie droite est vide, l’élément n’est pas dans le tableau et la réponse est : Non.

Déroulé sur l’exemple, à la main.

T=[0,1,2,...,9]. On cherche 3.

1. On propose : 4.

   4 > 3 donc on recommence avec la partie avant 4 : T1 = [0,1,2,3]

Déroulé sur l’exemple, à la main.

T=[0,1,2,...,9]. On cherche 3.

1. On propose : 4.

   4 > 3 donc on recommence avec la partie avant 4 : T1 = [0,1,2,3]

2. On propose : 2

   2 < 3 donc on recommence avec la partie après 2 : T2 = [3]

Déroulé sur l’exemple, à la main.

T=[0,1,2,...,9]. On cherche 3.

1. On propose : 4.

   4 > 3 donc on recommence avec la partie avant 4 : T1 = [0,1,2,3]

2. On propose : 2

   2 < 3 donc on recommence avec la partie après 2 : T2 = [3]

3. On propose : 3

   3 = 3 donc on a trouvé l’élément et la réponse est : Oui, 3 est dans T.

L’algorithme

rechercheDicho(liste, clé)
  bas = 0
  haut = longueur(liste) - 1
  Tant que (bas < haut) :
      med = (bas + haut) // 2
      si clé == liste[med]:
          bas = med
          haut = med
      sinon si clé > liste[med]: bas = med + 1
      sinon: haut = med - 1
  si cle == liste[bas]: renvoyer Vrai
  sinon: renvoyer Faux

Même exemple, avec les variables

Voici un déroulé de l’algorithme à la main.

Notre tableau T est [0, 1, 2, ..., 9] et on cherche 3.

On dispose des variables :

• début, milieu, fin qui sont des éléments du tableau
• trouvé qui est un booléen (vrai / faux)
• et val > milieu (booléen, qui va nous aider à choisir)

On présent les éléments dans une table :

Même exemple, avec les variables

Voici un déroulé de l’algorithme à la main.

Notre tableau T est [0, 1, 2, ..., 9] et on cherche 3.

• Avant la boucle. début, fin et trouvé sont initialisées (0, 9, faux). La variable milieu et le booléen val > milieu n’existent pas encore.

Même exemple, avec les variables

Notre tableau T est [0, 1, 2, ..., 9] et on cherche 3.

1. Premier tour. On descend début et fin.

   On calcule milieu (0+9)/2 = 4.5 dont la partie entière est 4. Donc milieu = 4.

   Est-ce que 3==4 ? Faux.

   Est-ce-que “3>4” ? Faux. Dans ce cas, c’est fin qui prend la valeur de milieu

Même exemple, avec les variables

Notre tableau T est [0, 1, 2, ..., 9] et on cherche 3.

2. Second tour. On a descendu début, on donne à fin la valeur précédente de milieu (4). Et on calcule les nouveaux éléments. milieu = (0+4)/2 = 2 (entier).

Est-ce-que 3==2 ? Faux.

Est-ce-que 3>2 ? Vrai. Dans ce cas, c’est début qui change et prend la valeur de milieu + 1.

Même exemple, avec les variables

Notre tableau T est [0, 1, 2, ..., 9] et on cherche 3.

3. Troisième tour. On a descendu la valeur de fin et donné à début l’ancienne valeur de milieu + 1 (3). Et on recommence.

   Milieu = (3 + 4)/2 = 3.5 dont la partie entière est 3. Est-ce-que 3==3 ? VRAI !!!

L’algorithme est terminé et la sortie est “VRAI”. Le nombre 3 est bien un élément du tableau [0, 1, 3, 4, 5, …, 9].

Conclusion

• La recherche dichotomique permet de gagner beaucoup d’étape par rapport au parcours séquentiel du tableau.

• Elle nécessite d’avoir un tableau trié sans quoi on ne peut l’appliquer.

Remarques sur la complexité

• Si on ne souhaite l’appliquer qu’une seule fois, il n’est pas toujours intéressant de trier de le tableau pour chercher. C’est généralement trop long…
• Mais si on doit souvent effectuer des recherches dans le tableau, alors c’est indispensable.

Nombre d’étapes

• parcours séquentiel : autant que d’éléments dans le tableau dans le pire des cas. Le parcours séquentiel prend (dans le pire des cas) $n$ étapes.
• recherche dichotomique (après le tri) : $\log_2 n$ étapes. $\log_2 n$ est (grosso modo) le nombre de divisions entières de $n$ par 2 qu’on peut effectuer avant de trouver un quotient nul.