Recherche dichotomique

Activité

1) En vous mettant par deux, jouez chacun deux fois à trouver un nombre entre 1 et 100. À chaque proposition, l’autre doit dire « plus grand » ou « plus petit ». Notez le nombre d’essai pour chaque partie.

2) Quelle est selon vous la meilleure stratégie ?

Il faut proposer le milieu de l'intervalle restant.

Nous allons voir un algorithme de recherche dans un tableau qui est similaire au problème précédent. L’algorithme suivant s’utilise dans un tableau trié !

Algorithme de recherche dichotomique

Voici l’algorithme :

VARIABLE
t : tableau d'entiers trié
mil : nombre entier
fin : nombre entier
deb : nombre entier
x : nombre entier // x : l'entier recherché
tr : booléen
DEBUT
tr ← FAUX
deb ← 1
fin ← longueur(t)
tant que tr == FAUX et que deb ⩽ fin :
    mil ← partie_entière((deb+fin)/2)
    si t[mil] == x :
        tr = vrai
    sinon :
        si x > t[mil] :
            deb ← mil+1
        sinon :
            fin ← mil-1
        fin si
    fin si
fin tant que
renvoyer la valeur de tr
FIN

Fonctionnement

3) Déroulons cet algorithme sur le tableau t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] avec la recherche de x = 35.

tr = faux
deb = 1
fin = 10
tr == faux et deb ≤ fin : on rentre dans la boucle
mil = 5
t[5] = 23 ≠ 35 : on ne rentre pas dans le si
35 > t[5] : on entre dans le si
deb = 6
retour au début de la boucle

tr = faux
deb = 6
fin = 10
tr == faux et deb ≤ fin : on rentre dans la boucle
mil = 8
t[8] = 40 ≠ 35 : on ne rentre pas dans le si
35 < t[8] : on n’entre pas dans le si
fin = 7
retour au début de la boucle

tr = faux
deb = 6
fin = 7
tr == faux et deb ≤ fin : on rentre dans la boucle
mil = 6
t[6] = 27 ≠ 35 : on ne rentre pas dans le si
35 > t[6] : on entre dans le si
deb = 7
retour au début de la boucle

tr = faux
deb = 7
fin = 7
tr == faux et deb ≤ fin : on rentre dans la boucle
mil = 7
t[7] == 35 : on rentre dans le si
tr = vrai
retour au début de la boucle

tr == vrai : on ne rentre pas dans la boucle
renvoyer vrai

4) On peut également dérouler l’algorithme de deux autres façons avec des schémas utilisant le tableau :

5) Reproduire le déroulement de l’algorithme avec un schéma en prenant t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 9.

6) Reproduire le déroulement de l’algorithme avec un schéma en prenant t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 40.

Complexité

7) Déterminons la complexité de cet algorithme.

Nous avons un tableau de taille n. On suppose qu'il existe un entier k tel que n = 2^k. (Sinon, il faut travailler avec des inégalités)

À la première découpe, le nouveau tableau a une taille 2^k-1. À la k^e le tableau a une taille 2^k-k = 2⁰ = 1. L'algorithme est alors terminé car nous avons soit trouvé le nombre, soit trouvé qu'il n'était pas présent. Nous avons effectué k passages dans la boucle. La complexité est alors O(k)

Or n = 2^k, donc log(n) = log(2^k) = k log(2) = k. Donc la complexité est O(log(n)).

La complexité est donc meilleure que O(n). Mais celà est dû au fait que le tableau est préalablement trié.

Terminaison

8) Pour montrer que cet algorithme se termine nous allons utiliser un variant de boucle.

9) Créez une fonction utilisant la recherche par dichotomie et comparez sa performance avec le mot clé in. Vous créerez un tableau trié de 10000 éléments et calculerez le temps de recherche pour les deux méthodes sur le même tableau.