- Valeur cherchée
- Encore possibles
- Comparées
- Écartées
- Trouvées
Recherche dichotomique
La recherche dichotomique trouve une valeur dans une liste triée en regardant toujours au milieu. Si la valeur du milieu est trop petite, la cible ne peut être qu'après ; si elle est trop grande, seulement avant. Dans les deux cas, la moitié de ce qui reste est écartée. Choisissez la valeur à chercher, avancez étape par étape et regardez la zone ombrée rétrécir jusqu'à ce que la cible soit trouvée ou qu'il ne reste rien. Appuyez sur Lecture pour regarder la recherche, ou sur Étape et Retour pour avancer d'une étape à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. La ligne pointillée marque la valeur cherchée, et la zone ombrée montre où elle peut encore se trouver. La recherche dichotomique exige une liste triée : une liste non triée est donc d'abord triée. Choisissez la valeur, le nombre de barres, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Choisissez la valeur à chercher et le nombre de barres. Ou saisissez vos propres nombres : la recherche dichotomique les trie d'abord.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une étape à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans la recherche.
- Comparez la tuile Comparaisons à « La recherche linéaire demanderait », pour une valeur proche de la fin ou absente.
Comment fonctionne la recherche dichotomique
Gardez en tête la partie de la liste triée qui peut encore contenir la cible ; au départ, c'est toute la liste. Regardez la valeur en son milieu. Si elle est égale à la cible, c'est fini. Si elle est plus petite, la cible ne peut être qu'après : continuez avec la partie qui suit le milieu. Si elle est plus grande, continuez avec la partie qui le précède. Quand il ne reste rien, la cible n'est pas dans la liste.
Pourquoi elle est si rapide
Chaque comparaison divise par deux la partie qui reste. En partant de n valeurs, il en reste au plus environ n/2ᵏ après k comparaisons, donc la recherche se termine en au plus ⌊log₂ n⌋ + 1 comparaisons : 6 pour 40 valeurs, 10 pour 1 000, 20 pour un million. La recherche linéaire peut devoir examiner chaque valeur. Le hic : la liste doit être triée, et la garder triée, ou la trier d'abord, a son propre coût.
Questions fréquemment posées
Comment fonctionne la recherche dichotomique ?
Elle compare la cible à la valeur du milieu de la partie d'une liste triée qui peut encore la contenir. Si elles sont égales, la cible est trouvée ; sinon, la moitié qui ne peut pas la contenir est écartée, et la recherche continue dans l'autre moitié jusqu'à trouver la cible ou jusqu'à ce qu'il ne reste rien.
Combien de comparaisons faut-il à la recherche dichotomique ?
Au plus ⌊log₂ n⌋ + 1 pour une liste de n valeurs : 6 pour 40, 10 pour 1 000, 20 pour un million. Chaque comparaison divise le reste par deux.
Pourquoi la recherche dichotomique exige-t-elle une liste triée ?
Parce que seule une liste triée permet à une comparaison de dire de quel côté se trouve la cible. Dans une liste non triée, une valeur plus petite au milieu ne dit rien sur la position de la cible, donc rien ne peut être écarté.
Quelle valeur trouve-t-elle en cas de doublons ?
N'importe laquelle, selon où tombent les milieux. Les variantes qui continuent à chercher à gauche ou à droite après une correspondance trouvent la première ou la dernière occurrence.
Mes nombres sont-ils envoyés quelque part ?
Non. La recherche s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur