GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Recherche dichotomique ======

Considérons un tableau ''T'' et une valeur ''needle'' que l'on souhaite trouver dans le tableau.

<WRAP important>La recherche dichotomique nécessite que ''T'' soit **trié**. Dit autrement, <wrap box>**Précondition :** ''T'' est trié.</wrap></WRAP>

<WRAP important>L'algorithme de recherche dichotomique est à connaître.</WRAP>


===== Algorithme =====

<code lang-none>
ENTRÉES : T, needle
DÉBUT
    a = 0 et b = dernier indice de T
    TANT QUE a < b FAIRE
        m = indice au milieu de a et b, arrondi par défaut au besoin
        SI valeur en m >= needle ALORS
            continuer la recherche à gauche : b prend la valeur m
        SINON
            continuer la recherche à droite : a prend la valeur m + 1
        FIN SI
    FIN TANT QUE
    SI valeur en a est needle ALORS
        RENVOYER a
    SINON
        RENVOYER -1
    FIN SI
FIN
</code>

<WRAP box>
Implémentez en Python la fonction ''%%recherche_dichotomique(T, needle)%%'' faisant la traduction de cet algorithme.

Ajoutez les tests suivants
<code python>
T = [1, 5, 13, 15, 15, 41, 43, 58, 58, 75, 89, 101]
assert recherche_dichotomique(T, 22) == -1
assert recherche_dichotomique(T, 41) == 5
assert recherche_dichotomique(T, 15) == 3
assert recherche_dichotomique(T, 58) == 7
assert recherche_dichotomique(T, 122) == -1
assert recherche_dichotomique(T, 0) == -1
assert recherche_dichotomique([], 45) == -1
</code>
</WRAP>

===== Correction =====

Les tests précédents nous invitent à croire que la fonction est correcte. Mais comment être certain que c'est le cas pour n'importe quel tableau ?

==== Terminaison ====

La fonction contient une boucle ''TANT QUE''. C'est le seul élément à problème. Nous devons nous assurer que la condition de cette boucle finit devenir fausse de sorte que la boucle se termine.

Pour cela, on considère une quantité et on vérifie que cette quantité change toujours dans le même sens.

<WRAP box>
  * Justifiez que la quantité ''%%b - a%%'' diminue d'au moins 1 à chaque répétition de la boucle ''while''.
  * Déduisez-en que la boucle se termine.
</WRAP>

<WRAP tip>La quantité ''%%b - a%%'' qui nous a aidé dans ce raisonnement est appelée **variant de boucle**.
</WRAP>

==== Correction ====

<WRAP box>
  * Que se passe-t-il si ''T'' est vide ?
  * Comment corriger ce problème ?
</WRAP>

Cela vous montre qu'on peut facilement oublier des cas à problème. Il faut toujours réfléchir à ces cas limites.

Supposons maintenant que le problème précédent à été résolu.

<WRAP box>
On considère la portion de ''T'' allant des indices ''a'' à ''b'' inclus. On peut la noter ''Tab''.
  * Justifiez qu'au début de l'algorithme, ''T'' et ''Tab'' sont identiques.
  * Justifiez que si ''needle'' est dans ''Tab'' au début d'un tour d'exécution de ''while'', alors ''needle'' est toujours dans ''Tab'' à la fin de l'exécution.
  * À quoi se réduit ''Tab'' en fin de boucle ?
  * Justifiez que la fonction est correcte.
</WRAP>

<WRAP tip>
On adopte ici un raisonnement assez rigoureux pour être convainquant. On pourrait aller plus loin et utiliser un langage aussi rigoureux qu'une démonstration mathématique. Tous les programmeurs ne font pas ce travail. Beaucoup de logiciels sont produits sans que l'on vérifie la correction des fonctions. Souvent, les contraintes commerciales obligent à aller vite, d'où la présence de nombreuses failles.

Néanmoins, il est possible de faire ce travail et on le fait dans les cas où la sécurité est essentielle.

Attention cependant, vous pouvez écrire un programme Python exempt de failles, cela n'empêchera pas que Python a lui-même des failles qui pourront être exploitées ! Par exemple, certaines failles de sécurité exploiteront des défauts de gestion de la mémoire, ces défauts existant dans le langage de programmation lui-même.
</WRAP>

===== Performances =====

Le temps d'exécution de la fonction dépend essentiellement du nombre de répétition de la boucle TANT QUE.

<WRAP box>
  * Si le tableau contient 16 éléments. Combien de fois se répète la boucle ?
  * Est ce que l'on peut avoir de la chance et avoir une fin plus rapide ?
  * Et si le tableau compte 32 éléments ? 64 ? 128 ?
  * En général, comment évolue le nombre d'exécution de la boucle quand ''n'' est multiplié par 2 ?
</WRAP>