Informatique · La recherche dichotomique
Comment trouver un nom parmi un million en 20 étapes ?
Ce que vous verrez
Un annuaire contient un million de noms, par ordre alphabétique. Les vérifier un par un pourrait demander un million de coups d'œil. Peut-on faire mieux ? Ouvrez-le pile au milieu. Le nom cherché vient après, donc toute la première moitié disparaît. Il en reste un demi-million. Ouvrez le milieu de ce qui reste, et coupez encore en deux. Et encore. Chaque coup d'œil élimine la moitié de ce qui reste. Vingt coupes en deux font passer un million à un seul nom, parce que deux puissance vingt dépasse tout juste le million. Un milliard de noms ? Seulement dix coups d'œil de plus.
