ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Recherche dichotomique et logarithme népérien      Dichotomie et équation f(x) = 0

Dans un fichier informatique les données sont alphanumériques, c'est à dire numériques ou alphabétiques ou encore mixtes (comme, par exemple, l'immatriculation d'un véhicule). L'ordinateur traite généralement les données comme étant alphanumériques : les caractères, lettres ou chiffres sont codés de 0 à 255 (code ASCII = American Standard Code for Information Interchange).

Pour la recherche de données dans un fichier informatique trié, il est une méthode efficace, dite dichotomique :

Si N est le nombre de fiches, on se propose de montrer que le temps de recherche par la méthode dichotomique est sensiblement proportionnel au
logarithme de N et non à N comme pour la méthode séquentielle : dans une telle recherche, on parcourt le fichier du début à la fin. dans ce cas, le nombre moyen de recherches est (N+1)/2. En effet, la fiche cherchée est peut-être en tête : 1 recherche, en deuxième position : 2 recherches, ..., ou en queue : n recherches...

La moyenne est donc (1 + 2 + ... + N)/N. Or 1 + 2 + ... + N = N(N+1)/2, d'où le résultat.

La recherche dichotomique consiste en des découpages du fichier de moitié en moitié : on compare le code alphanumérique f de la fiche cherchée à celui df de la dernière fiche de la moitié inférieure :

La première moitié a pour effectif maximum N/2 (p=1). Si l'on n'est pas "tombé" dans la bonne moitié, on continue la recherche dans la seconde moitié (p=2) sur 1/2 N/2 = N/22 fiches (au maximum). Et ainsi de suite.

Le nombre maximum de recherche est alors le plus grand entier p tel que 2p N.

 Si N est impair, comme 127, l'ordinateur choisira la partie entière de 127/2 soit 63, la seconde moitié sera constituée des 64 dernières fiches. Ceci explique que 2p n'est pas égal à N.

L'entier p vaut donc sensiblement ln N/ln 2 = log2N (ln désignant le logarithme népérien et log2 désignant le logarithme de base 2 ). On en déduit que le nombre moyen de recherches est sensiblement : (1 + 2 + ... + p)/p = (p + 1)/2, c'est à dire :


Si un micro-ordinateur met, en moyenne, 3 minutes pour rechercher une fiche parmi 24 000 par la méthode séquentielle,
combien mettrait-il de temps (théoriquement) par la méthode dichotomique ?

Réponse :   Pour 24 000 fiches, la méthode séquentielle fera 12000 recherches (à une demi-recherche près...). Ceci en 180 secondes. La méthode dichotomique ne fera que 8 recherches (7,7...), ce qui conduit, en admettant la proportionnalité, à seulement environ 1/10e de seconde, 1800 fois plus rapide !

 Ce n'est bien sûr là qu'un résultat théorique. En fait le temps sera plus long car il faut tenir compte, en particulier, de la plus grande complexité du programme.


© Serge Mehl - www.chronomath.com