Comme expliqué au début de la séquence précédente, le fait qu'un tableau soit trié, par exemple par ordre croissant, facilite de nombreuses opérations.
L'une d'entre elles est la recherche d'un élément. En effet, ii suffit de comparer la valeur recherchée avec la valeur située au milieu du tableau.
Si elle est plus petite, on peut restreindre la recherche à la moitié gauche du tableau. Sinon, on la restreint à la moitié droite du tableau.
En répétant ce procédé, on divise la zone de recherche par deux à chaque fois 1. Tres rapidement, on parviendra soit à la valeur recherchée, soit à un intervalle devenu vide. On appelle cela la recherche dichotomique.
On connait tous ce principe, pour l'avoir appliqué étant enfant pour deviner un nombre en ayant comme réponses à nos tentatives \"c'est plus petit\" ou \"c'est plus grand\". Ce principe est connu en informatique sous le nom de diviser pour mieux régner et il est appliqué dans de nombreux algorithmes.
La recherche dichotomique en est l'expression la plus simple.
Pour fixer les idées, supposons que l'on souhaite définir une fonction qui recherche la valeur v dans le tableau t.
def recherche_dichotomique( t , v):
Le tableau t est supposé trié par ordre croissant. Cette fonction pourrait se contenter de renvoyer un booléen indiquant la présence de v dans t.
Cependant, on va faire un effort supplémentaire, en renvoyant une position dans le tableau t à laquelle se trouve la valeur v, le cas échéant. II se pose donc la question de savoir ce que va renvoyer notre fonction lorsque la valeur v n'apparait pas dans le tableau t.
On choisit ici de renvoyer la valeur None dans ce cas.
Pour mettre en oeuvre la recherche dichotomique, on va délimiter la portion du tableau t dans laquelle la recherche est actuellement réduite à l'aide de deux indices g et d.
Initialement, ces deux indices délimitent l'intégralité du tableau.
g = 0
d = len(t) - 1
On peut se représenter la situation courante avec le petit dessin suivant.
0 g d
t = [éléments < v, .... ..........., éléments > v]
Le programme va alors répéter le principe de dichotomie tant que cette portion n'est pas vide, c'est-à-dire tant que la condition g <= d est vraie. On le fait avec une boucle while.
while g <= d:
# invariant : 0 <= g et d < len(a)
# invariant : v ne peut .se trouver que clans t
II faut maintenant examiner l'élément central pour prendre notre décision. On calcule sa position dans une variable m, en faisant la moyenne de g et d.
m = (g + d) // 2
Attention à bien utiliser ici la division entière, c'est-a-dire l'opération // et non pas l'operation /, sans quoi on pourrait obtenir des valeurs décimales comme 2.5 et ensuite une erreur lors de l'accès au tableau t.
Une fois la valeur de m calculée, ii faut se représenter ainsi la situation.
0 g m d
t = [éléments < v, ...... , ? , ...... éléments > v]
On va maintenant comparer v à t[m] et il y a trois cas possible pour la valeur v :
- v est plus grande;
- v est plus petite;
- v est égale à la valeur t[m].
Si elle est plus grande, alors la recherche peut se restreindre à la moitié droite.
On modifie donc la valeur de g en conséquence.
if t[m] < v:
g = m + 1
Si en revanche elle est plus petite, on se restreint à la moitié gauche.
On modifie donc la valeur de d en conséquence.
if t[m] > v:
d = m - 1
Si enfin les deux valeurs sont egales, c'est qu'on a trouve une occurrence de la valeur v.
On renvoie alors l'indice m comme résultat de la fonction.
else :
return m
Il se peut qu'on finisse par sortir de la boucle, parce que la condition g <= d n'est plus vraie. Cela signifie que la valeur v ne peut pas se trouver dans le tableau, car il ne contient plus que des valeurs strictement plus petites que v (à gauche) ou strictement plus grandes (à droite).
On renvoie alors None pour signaler l'échec de notre recherche dichotomique.
return None
Le code complet est donc le suivant :
def recherche_dichotomique(t, v):
\"\"\"renvoie une position de v dans le tableau t,
supposé trié, et None si v ne s'y trouve pas\"\"\"
g = 0
d = len(t) - 1
while g <= d:
# invariant : 0 <= g et d < len(t)
# invariant : v ne peut se trouver que dans t[g. d]
m = (g + d) // 2
if t[m] < v:
g = m + 1
elif t[m] > v:
d = m - 1
else:
return m
# la valeur ne se trouve pas dans le tableau
return None
Ecrire et tester le code précédent avec les instructions suivantes:
tab = [1,2,3,4,5,7,9,10,12,13,15,18,20]
print(\"tab=\",tab)
print(\"5 dans tab?\",recherche_dichotomique(tab,5))
print(\"18 dans tab?\",recherche_dichotomique(tab,18))
print(\"11 dans tab?\",recherche_dichotomique(tab,11))
Prenez le temps de bien comprendre le fonctionnement de cet algorithme, en déroulant l'exécution de chaque instruction.
Ecrire vos résultats ici.
Vérifions que le programme de dichotomie est correct.
Commençons par montrer que le programme ne va pas échouer en accédant au tableau t en dehors de ses bornes. Le seul accès au tableau t se fait à l'indice m, dans la boucle while. Cet indice m est calcule comme la moyenne (arrondie vers le bas) de g et d, dont on sait qu'ils vérifient l'inégalité g <= d car on est dans la boucle. Par ailleurs, l'inégalité 0 < g est un invariant de boucle, de même que l'inégalité d < len(t). Par conséquent, à l'intérieur de la boucle, on a toujours
0 < g < m < d <len(t)
cc qui garantit un accès légal au tableau t. Lorsque g ou d est modifié dans la boucle, on peut vérifier que les inégalités 0 < g et d < len(t) sont bien préservées.
L'étape suivante consiste à montrer que, si on renvoie un entier, alors ii s'agit bien d'une position où la valeur v apparait. C'est ce que l'on appelle la correction de l'algorithme. C'est immédiat, car l'instruction return m n'est effectuée que lorsque l'égalité t[m] = v est vérifiée. En effet, on vient de vérifier que les deux conditions t[m] < v et t[m] > v sont fausses.
II faut également montrer que, si on renvoie la valeur None, alors la valeur v n'apparaît pas dans le tableau t (sans quoi il suffirait de toujours renvoyer None). C'est ce que l'on appelle la complétude de l'algorithme. Elle est mêms évidente que la correction. En effet, nous pourrions avoir raté des éléments du tableau t par accident, par exemple si nous avions écrit g = m + 2 au lieu de g = m + 1. Pour montrer la complétude, on identifie l'invariant de boucle suivant :
la valeur v ne peut se trouver que dans t[g...d] .
C'est vrai initialement, car g et d sont initialisées à 0 et len(t) - 1 respectivement. Lorsque g ou d est modifié dans la boucle, on peut vérifier que cet invariant est bien préserve. Dans le premier cas, on a t[m] < v et on effectué g = m + 1. Or, le tableau étant trié, on a donc
t [g . .m-1] < t [m] <v
et donc la valeur v ne peut pas se trouver dans t[g..m] .
Elle ne peut donc se trouver que dans t [m+1 . d], c'est-à-dire t[g.. d]. On raisonne de même lorsque t[m] > v et que d prend la valeur m - 1.
Enfin, il convient de montrer que notre programme ce termine toujours. Si par exemple nous avions écrit
g = m au lieu de g = m + 1, alors absolument tout ce que nous venons de démontrer ci-dessus resterait valable, mais le programme ne se terminerait plus dans certains cas. Pour montrer que notre programme se termine toujours, on peut remarquer que la valeur entière d — g est un variant:
elle décroit d'au moins une unité à chaque itération de la boucle while, tout en restant positive ou nulle (car g < d dans la boucle).
Elle ne peut décroitre infiniment. On finira donc par avoir d < g et une sortie de boucle, si on n'a pas trouvé la valeur v avant cela.
Pour mesurer l'efficacité de la recherche dichotomique, on peut s'intéresser au nombre de valeurs du tableau t qui ont été examinées pendant l'exécution de la fonction recherche_dichotomique(t, v).
C'est exactement le nombre d'itérations de la boucle while ou encore le nombre de valeurs prises par la variable m, puisque chaque itération de la boucle affecte une valeur différente à la variable m et examine l'élément t[ml.
Le temps d'exécution de recherche_dichotomique est directement proportionnel à ce nombre. L'exercice 3 propose d'instrumenter le programme recherche_dichotomique pour afficher ce nombre.
Plaçons-nous dans le pire cas, lorsque la valeur v n'apparait pas dans le tableau t, ce qui nous oblige à répéter la boucle jusqu'à ce que l'intervalle soit vide. Prenons l'exemple d'un tableau de taille 100.
A la première itération, on va se restreindre à un sous-tableau contenant 49 ou 50 éléments, selon le coté choisi.
Prenons le cas le moins favorable, avec 50 éléments.
A la seconde itération, on va se retrouver avec au plus 25 éléments, puis au plus 12 à la suivante, et ainsi de suite.
Au total, on ne fera jamais plus de 7 tours de boucle. Ii suffit donc d'examiner au plus 7 valeurs parmi les 100. De la même manière, on peut montrer que 20 itérations sont toujours suffisantes, dans le pire des cas, pour rechercher une valeur dans un tableau d'un million d'éléments.
On peut le déterminer empiriquement en répétant des divisions par deux en partant d'un million, jusqu'à obtenir 0.
Inversement, et plus rigoureusement, on peut chercher la plus petite puissance de 2 qui dépasse la taille du tableau.
Ainsi, les valeurs données ci-dessus s'expliquent par 27 > 100 et 220 > 106.
De manière générale, pour un tableau t de taille n, le temps d'exécution de recherche_dichotomique(t, v) est dans le pire des cas égal au plus petit entier k tel que
2k > n.
Le tableau ci-dessous donne quelques valeurs de k en fonction de n.
| n | k |
| 10 | 4 |
| 100 | 7 |
| 1 000 | 10 |
| 1 000 000 | 20 |
| 1 000 000 000 | 30 |
Comme on le constate, le nombre k d'étapes croit très lentement avec la taille n du tableau.
II existe une fonction mathématique, appelée logarithme, qui permet d'exprimer et de calculer k à partir de n. Mais elle n'est pas au programme de mathématiques de première général.
Pour 1 milliard d'éléments, on a seulement besoin d'examiner 30 valeurs dans le pire des cas, ce qui veut dire que notre recherche dichotomique sera instantanée. C'est donc là un algorithme extrêmement efficace.
Combien de valeurs sont examinées lors d'un appel recherche_dichotomique( [0,1,1,2,3,5,8,13,21] , 7) ?
Ecrire ici la solution.
Donner un exemple d'exécution de recherche_dichotomique où le nombre de valeurs examinées est exactement quatre.
Ecrire ici la solution.
Modifier le programme recherche_dichotomique pour afficher le nombre total de tours de boucle effectués par l'algorithme.
Lancer le programme sur des tableaux de tailles différentes (par exemple 100, 1000, etc.) et observer les nombres de tours affichés.
On pourra par exemple chercher la valeur 1 dans un tableau ne contenant que des valeurs 0, ce qui correspond au pire cas.
","title":"Exercice 3"},{"edit":" Ecrire ici la solution.
Ecrire une fonction nb_de_tours(n) qui renvoie le plus petit entier k tel que 2k > n, c'est-à-dire le nombre maximal de valeurs examinées par la recherche dichotomique dans un tableau de taille n.
","title":"Exercice 4"},{"edit":"Ecrire ici la solution.
Quand on joue à deviné un nombre avec un nombre compris entre 1 et 100, combien faut-il d'essais dans le pire des cas si l'on joue de manière optimale?
","title":"Exercice 5"},{"edit":"Ecrire ici la solution.
Ecrire un programme qui permette à l'ordinateur de jouer contre l'utilisateur pour retrouver un nombre.
L'utilisateur choisira un nombre entre 0 et cent et l'ordinateur devra le trouver, le plus efficacement possible. A chaque proposition faite par l'ordinateur, l'utilisateur devra donner une réponse sous la forme d'une chaine de caractères parmi \"plus grand\", \"plus petit\" ou \"bravo\".
","title":"Exercice 6"},{"edit":"Ecrire ici la solution.