Recherche dichotomique

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

La recherche dichotomique nécessite que T soit trié. Dit autrement, Précondition : T est trié.

L'algorithme de recherche dichotomique est à connaître.

Algorithme

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

Implémentez en Python la fonction recherche_dichotomique(T, needle) faisant la traduction de cet algorithme.

Ajoutez les tests suivants

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

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.

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.

La quantité b - a qui nous a aidé dans ce raisonnement est appelée variant de boucle.

Correction

Que se passe-t-il si T est vide ?
Comment corriger ce problème ?

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.

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.

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.

Performances

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

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 ?