La recherche dichotomique : comment l'expliquer à un enfant
La recherche dichotomique avec le jeu du nombre à deviner : pourquoi 7 questions suffisent pour 100 nombres, à quoi ressemble l'algorithme pas à pas et quelles erreurs font les enfants.
Mis à jour:
La recherche dichotomique est l'un des premiers algorithmes où l'enfant voit qu'une méthode astucieuse bat la patience. Le plus simple est de commencer par un jeu.
Le jeu : devine le nombre
Pensez à un nombre de 1 à 100. L'enfant devine, et vous répondez seulement « trop petit », « trop grand » ou « trouvé ».
Au début, les enfants tirent au hasard ou demandent dans l'ordre : 1, 2, 3… Demandez alors par quel nombre il vaut mieux commencer pour éliminer à coup sûr le plus de nombres possible. La réponse, c'est le milieu : 50.
Pourquoi le milieu
Après la question sur 50, il reste la moitié des nombres, quelle que soit la réponse. Après la question suivante, un quart. L'intervalle diminue ainsi : 100, 50, 25, 13, 7, 4, 2, 1. Cela fait sept questions. Pour mille nombres, dix suffisent, et pour un million, vingt.
En demandant dans l'ordre, il faudrait dans le pire des cas cent questions.
L'algorithme pas à pas
- Retiens les deux bouts de l'intervalle :
gaucheetdroite. - Calcule le milieu.
- Si le milieu est le nombre cherché, c'est fini.
- S'il est trop petit, déplace
gauchejuste après le milieu. S'il est trop grand, déplacedroitejuste avant le milieu. - Retourne à l'étape 2.
C'est une boucle avec une décision à l'intérieur et deux variables qui se rapprochent l'une de l'autre.
À quoi ça sert
- Chercher un mot dans un dictionnaire papier : on ouvre au milieu et on sait dans quel sens aller.
- Chercher une page dans un livre.
- Deviner une taille, un prix, une date.
Il y a une seule condition : les données doivent être triées.
Les erreurs fréquentes
- L'intervalle ne diminue pas. Si
gauchese déplace sur le milieu et non après le milieu, la boucle peut tourner sans fin. - Les données ne sont pas triées. L'algorithme élimine alors une moitié où la réponse pouvait se trouver.
- Le nombre cherché n'existe pas. La boucle doit s'arrêter quand
gauchedépassedroite.
Dans Looponi
La recherche dichotomique est l'un des algorithmes du parcours « Bâtisseurs » (12–15 ans). L'élève la construit sous forme d'algorigramme, parie sur le nombre de tours que fera la boucle et regarde les bouts de l'intervalle se rapprocher à chaque étape.
Questions fréquentes
Qu'est-ce que la recherche dichotomique ?
C'est une façon de chercher dans des données triées, où chaque question élimine la moitié des possibilités. On regarde le milieu, puis on va à gauche ou à droite.
Combien de questions faut-il pour deviner un nombre de 1 à 100 ?
7 au maximum. Chaque question réduit l'intervalle de moitié : 100, 50, 25, 13, 7, 4, 2, 1.
Pourquoi les données doivent-elles être triées ?
Parce que c'est seulement dans ce cas que la réponse « trop petit » ou « trop grand » dit quelle moitié on peut éliminer. Dans des données mélangées, il faut vérifier une par une.
À partir de quel âge peut-on l'apprendre ?
Un enfant de huit ans comprend déjà le jeu du nombre à deviner. L'algorithme lui-même, avec des variables, vaut la peine d'être introduit vers 12–13 ans.