Comparaisons en recherche binaire
Calculateur

Entrées

Comparaisons au pire cas
20

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 cas20
log₂ N exact19.931568
Gain vs recherche linéaire50,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.

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.