Deviner un nombre entre 1 et 1 000
Deviner un nombre entre 1 et 1 000 demande au plus 10 questions avec la dichotomie.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Dichotomie, pire cas
- 10 étapes
- Recherche linéaire, pire cas
- 1 000 étapes
- Recherche linéaire, cas moyen
- 501 étapes
- Gain au pire cas
- × 100
La dichotomie suppose une liste déjà triée.
Le cas en détail
À chaque question « est-ce plus grand ? », on élimine la moitié des possibilités. 1 000 devient 500, 250, 125... jusqu'à 1 en 10 étapes. Une recherche linéaire demanderait jusqu'à 1 000 essais.
À retenir : C'est le principe du jeu du plus ou du moins : en posant toujours la question du milieu, on gagne en 10 coups.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments de la liste triée : 1000
- Dichotomie, pire cas
- 10 étapes
- Recherche linéaire, pire cas
- 1 000 étapes
- Recherche linéaire, cas moyen
- 501 étapes
- Gain au pire cas
- × 100
La dichotomie suppose une liste déjà triée.
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
La recherche dichotomique compare l'élément cherché au milieu de la liste triée et élimine la moitié à chaque étape : au pire, il faut plancher(log2 n) + 1 étapes. La recherche linéaire parcourt la liste : au pire n étapes, en moyenne environ n / 2 si l'élément est présent.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.