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.