Aller au contenu
Omnikalc

Calculateur d’étapes de recherche dichotomique

Saisissez le nombre d’éléments triés et la durée d’une comparaison pour obtenir le nombre d’étapes maximal et moyen d’une recherche dichotomique et le gain par rapport à un balayage linéaire.

Mis à jour le
Vos paramètres

Valeur hors limites

ns

Valeur hors limites

Résultats

Comparaisons dans le pire cas

20

Comparaisons moyennes pour une recherche réussie
18,93
Comparaisons moyennes pour un balayage linéaire
500 001
Durée d’une recherche dichotomique (pire cas)
1,000 µs
Durée d’un balayage linéaire (moyenne)
25,00 ms
Gain en nombre de comparaisons
26 411 ×

Le calculateur de recherche dichotomique donne le nombre maximal et moyen de comparaisons nécessaires pour trouver un élément dans une liste triée, et le compare à un balayage linéaire.

Comment se fait le calcul

  • Saisissez le nombre d’éléments triés.
  • Saisissez la durée d’une comparaison.
  • Le calculateur donne les étapes dans le pire cas, les étapes moyennes, la moyenne du balayage linéaire, les durées et le gain.

Exemple

Pour 1 000 000 d’éléments triés, une recherche dichotomique demande au plus ⌈log2(1 000 001)⌉ = 20 comparaisons et environ 18,93 en moyenne. Un balayage linéaire en demande 500 000 en moyenne. À 50 ns par comparaison, la recherche dichotomique prend 1,000 µs et le balayage 25,00 ms, soit environ 26 411 fois plus de comparaisons.

Pourquoi c’est utile

Le calculateur aide les étudiants en programmation, les développeurs et les candidats aux entretiens à voir pourquoi la recherche logarithmique passe si bien à l’échelle et à estimer des durées de recherche dans des tableaux et des index triés.

À savoir

La même idée de division par deux s’applique aux jeux de devinettes, à la bissection en débogage, par exemple pour trouver quel commit a cassé une compilation, et à la recherche de racines. Pour trouver le nombre d’essais nécessaires pour identifier un nombre de 1 à 100, saisissez 100 et lisez 7 comme pire cas. Notez que sur du matériel réel, la durée par comparaison n’est pas constante : les premières étapes touchent une mémoire en cache, tandis que les dernières sur un énorme tableau peuvent manquer le cache, donc les durées mesurées sont plus grandes que l’estimation simple. Pour des données sur disque, un arbre à nœuds larges, comme un arbre B, fait le travail avec moins de lectures. Une table de hachage donne un temps moyen constant mais ne garde pas l’ordre.

Outils liés

Le calculateur de collisions de hachage couvre les tables de hachage, celui de taille de la table des pages montre une autre structure logarithmique, celui du modèle roofline relie les déplacements de données à la vitesse et ceux de logarithme calculent directement le log2.

Questions fréquentes

Combien d’étapes demande une recherche dichotomique ?

Chaque comparaison divise par deux la plage de candidats, donc le pire cas est ⌈log2(n + 1)⌉ comparaisons. Pour 1 million d’éléments, c’est 20, et pour 1 milliard seulement 30. Le nombre augmente de un chaque fois que la liste double.

Quel est le cas moyen ?

Pour une recherche réussie où chaque élément est également probable, la moyenne est d’environ log2(n) − 1 comparaisons, un peu moins que le pire cas, car la moitié des éléments se trouvent au niveau le plus profond. Une recherche infructueuse prend environ le nombre du pire cas.

Quand un balayage linéaire est-il préférable ?

Pour des listes très courtes, de moins de 10 à 20 éléments environ, un balayage linéaire peut être aussi rapide ou plus rapide grâce à un code plus simple et au comportement du cache. La liste doit aussi être triée, et le tri coûte n log n, donc il n’est rentable que si l’on cherche de nombreuses fois.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.