II. La recherche dichotomique

Cours

Nous avons vu un algorithme de recherche d'élément dans un tableau, parcourant tous ces éléments jusqu'à trouver celui qui est recherché. Nous avons vu que sa complexité était en \(O(n)\) Cet algorithme n'a pas une complexité optimale.

On suppose que l'on a appliqué un algorithme de tri au tableau, avant de faire la recherche. L'algorithme de recherche dichotomique permet de faire une recherche plus efficacement.

A. Principe de l'algorithme

Les étapes de cet algorithme sont :

1. Comparer l'élément recherché avec la valeur du milieu du tableau :
   • si les valeurs sont égales, on a trouvé l'indice de l'élément recherché, l'algorithme s'arrête.
   • sinon si l'élément recherché est plus grand que le milieu du tableau, on continue de chercher l'élément dans la partie droite du tableau (où se trouvent les valeurs supérieures à celle du milieu).
   • sinon, on continue de chercher l'élément dans la partie gauche du tableau (où se trouvent les valeurs inférieures à celle du milieu).
2. On considère le milieu de la partie du tableau qu'il nous reste, et on réapplique l'étape 1, jusqu'à ce qu'on ait trouvé l'élément ou que le tableau soit vide.

Exemple

La recherche de 8 dans le tableau [1, 3, 4, 8, 9, 10, 11, 16, 25]. Compléter le schéma suivant avec les comparaisons faites à chaque étape :

B. Terminaison

Nous avons vu le code de cet algorithme en TD. Pour montrer que l'algorithme se termine, il faut montrer que la boucle non-bornée va s'arrêter.

Extrait du pseudo-code

tant que ind vaut -1 et debut inférieur ou égal à fin

Rôle de ind : stocker l'indice de l'élément recherché, ou bien -1 s'il n'est pas présent.
Rôle de debut et fin : délimiter les parties du tableau dans lesquelles on fait la recherche

L'algorithme s'arrête si :
- On trouve l'élément, dans ce cas ind aura une valeur différente de -1 et on sort de la boucle,
- Dans le cas où l'élément n'est pas présent, il faut s'assurer que la quantité fin-debut devient strictement négative. Cette quantité est un variant de boucle, c'est-à-dire que sa valeur décroît à chaque passage dans la boucle.

Prenons l'exemple de la recherche de 7 dans le tableau de la partie A.

Compléter comment la valeur des variables varie à chaque étape.

fin-debut décroît à chaque passage de boucle, et dans le pire des cas devient négative : on sort de la boucle.

C. Complexité

• Lorsque la taille du tableau double, on ne fait qu'une seule comparaison en plus lorsque l'on fait la recherche d'élément avec l'algorithme de recherche dichotomique.

  Exemple

  Recherche de 8 dans un tableau 2 fois plus grand que celui de la partie A.

  On ne rajoute qu'une étape !

  De manière générale, on cherche combien de fois il faut diviser par \(2\) pour n'avoir plus qu'une seule possibilité (c'est le pire des cas). On cherche donc a tel que \(n/2^a=1\).
  C'est-à-dire \(2^a= n\) La fonction \(log_2\) permet d'extraire \(a\) : \(log_2(2^a) = log_2(n)\)
  \(a = log_2(n)\)

  Sa complexité est donc en \(O(log_2(n))\).

• Les données devant être triées avant d'appliquer l'algorithme de recherche dichotomique, la complexité totale de l'algorithme correspond au maximum des complexités entre celle de l'algorithme de tri utilisé et \(O(log_2(n))\).