Comparaisons en recherche binaire
Calculateur
Résultats
- Comparaisons au pire cas
- 20
- log₂ N exact
- 19.931568
- Gain vs recherche linéaire
- 50,000
Résultats informatiques
| Comparaisons au pire cas | 20 |
| log₂ N exact | 19.931568 |
| Gain vs recherche linéaire | 50,000 |
Diagramme formula-map
- Comparaisons au pire cas
- 20
- log₂ N exact
- 19.931568
- Gain vs recherche linéaire
- 50,000
Relation informatique
Formule
comparisons = ⌈log₂ N⌉= 20
Note
Ceci est un modèle simplifié : il applique la formule informatique standard aux valeurs saisies et ignore la surcharge des protocoles, la variabilité de la compression, les reprises, la contention et d'autres effets réels. Dimensionnez vos systèmes avec des mesures réelles.
Exemple : avec les valeurs par défaut, calculator.technology.worst_case_comparisons vaut 20.
- Tableau : Tableau de conversion binaire, décimal et hexadécimal
- Tableau : Table ASCII (caractères imprimables)
Plus dans Technologie et informatique
Voir tout →Questions fréquentes
Combien de comparaisons faut-il pour une recherche dichotomique ?+
Au pire, il en faut ⌈log₂ N⌉, où N est le nombre d'éléments triés. Le calculateur arrondit log₂ N à l'entier supérieur.
Que montre la valeur exacte de log₂ N ?+
C'est le logarithme en base 2 de N, sans arrondi. Le nombre de comparaisons au pire est cette valeur arrondie à l'entier supérieur, car on ne peut pas faire une fraction de comparaison.
Comment la recherche dichotomique se compare-t-elle à la recherche linéaire ?+
Le calculateur divise N par le nombre de comparaisons dichotomiques au pire. Ce rapport indique à peu près combien de fois moins de comparaisons sont nécessaires que pour examiner chaque élément un par un.
La liste doit-elle être triée ?+
Oui. La formule suppose que les éléments sont déjà triés, car la recherche dichotomique divise l'intervalle restant par deux à chaque étape. Le calculateur ne le vérifie pas.
Est-ce le cas moyen ou le pire cas ?+
C'est le pire cas, comme l'indiquent le champ et la formule. Une recherche peut s'arrêter plus tôt si l'élément est trouvé plus vite, donc le nombre réel de comparaisons peut être inférieur.