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

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 préalablement trié, il est une méthode efficace, dite dichotomique : si N est le nombre de fiches, on se propose de montrer que le temps moyen 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 :

• si f ≤ df, alors la fiche est dans cette moitié; on la découpe en deux et on réitère le procédé;

• sinon elle est dans l'autre et on procède de la même façon dans la moitié supérieure : on la découpe en deux et on réitère le procédé.

La première moitié a pour effectif maximum N/2 (p=1).

 ➔  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.

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/4 fiches (au maximum), puis sur 1/2 × N/4 = N/8 fiches. Et ainsi de suite. Le nombre maximum de recherche p vérifie alors 1 ≤ N/2^p ≤ 2, c'est à dire 2^p ≤ N ≤ 2^p+1. Cette double condition est résoluble dans tous les cas : tout entier naturel non nul est compris entre deux puissances de 2. Et on peut écrire :

p × ln2 ≤ ln N ≤ (p + 1) × ln2

Ce que l'on peut aussi écrire :

p ≤ log₂ N ≤ p + 1

L'entier p vaut donc sensiblement log₂N (ln désignant le logarithme népérien et log₂ 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 :

• Dans le petit jeu de devinettes : "j'ai choisi un nombre entier entre 1 et 1000; trouve mon nombre pas essais successifs, je te dirai trop petit ou trop grand suivant tes propositions", on a 2⁹ < 1000 < 2¹⁰ ; un bon joueur amateur de calcul mental trouvera donc le bon nombre en moins de 10 coups. Et pour épater la galerie, il pourra trouver en 11 coups un entier entre 1 et 2000... jouer au pifomètre ne sera pas ici très efficace.

∗∗∗
Admettons qu'un un micro-ordinateur met 1 minute 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 N = 24 000 fiches, la méthode séquentielle procède, en moyenne, à (N+1)/2 recherches, soit 12 000 (à une demi-recherche près...). Ceci en 60 secondes. La méthode dichotomique ne fera que (1 + log₂N)/2 recherches, soit  7,7, arrondies à 8.
Ce qui conduit, en admettant la proportionnalité, à seulement environ 1/30e de seconde, 1800 fois plus rapide !

Stephen Cook et la complexité des algorithmes (informatique théorique) : »

 ➔  Ce n'est bien sûr là qu'un résultat théorique "moyen", qui ne vaut que si la fiche cherchée se trouve éloignée des premiers éléments. Voici un petit programme très éloquent comparant les deux méthodes de recherche dans une liste de un million de termes :