Recherche dichotomique contre recherche linéaire

Deviner un nombre entre 1 et 1 000 000 prend 20 questions si l'on coupe toujours en deux. Saisissez la taille de la liste et comparez avec un parcours un par un.

Jimenez JulienPar , éditeur de Calepin Binaire · mis à jour le

Dichotomie, pire cas
20 étapes
Recherche linéaire, pire cas
1 000 000 étapes
Recherche linéaire, cas moyen
500 001 étapes
Gain au pire cas
× 50 000

La dichotomie suppose une liste déjà triée.

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.

Questions fréquentes

Pourquoi la liste doit-elle être triée ?

Parce que la dichotomie raisonne sur l'ordre : comparer au milieu ne dit où chercher que si les valeurs sont rangées.

La dichotomie est-elle toujours préférable ?

Pour de petites listes ou une seule recherche, un parcours simple suffit. Trier coûte du temps, qui n'est rentable que si l'on cherche souvent.

Cas fréquents

Des exemples déjà remplis, avec leur explication :

Intégrer cet outil sur votre site

Copiez ce code pour afficher l'outil sur votre site ou votre blog. L'outil s'exécute dans le navigateur du visiteur, sans cookie ni suivi, et affiche un lien « Propulsé par Calepin Binaire » vers cette page.

Aperçu de la version intégrable : https://mircode.org/embed/recherche-dichotomique-contre-lineaire-etapes/

Les résultats sont fournis à titre indicatif. Pour aller plus loin, découvrez les sites de la catégorie Sandbox et casse-têtes de l'annuaire et lisez le guide de cette catégorie.

Autres outils

Voir les 35 outils