- Valeur cherchée
- Encore possibles
- Comparées
- Écartées
- Trouvées
Recherche par interpolation
La recherche par interpolation cherche une valeur dans une liste triée comme vous ouvrez un annuaire : pour un nom commençant par T, vous l'ouvrez vers la fin, pas au milieu. Elle estime la position de la valeur cherchée d'après les valeurs aux deux extrémités de la partie restante. Choisissez la valeur et la répartition, suivez les sondages pas à pas, et voyez quand l'estimation bat la recherche dichotomique et quand elle échoue. 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 partie ombrée montre où elle peut encore se trouver. La recherche par interpolation exige une liste triée, donc une liste non triée est d'abord triée. Choisissez la valeur, la répartition des valeurs, 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 à rechercher, la répartition des valeurs et le nombre de barres. Ou saisissez vos propres nombres : la recherche par interpolation 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.
- Réglez « Répartition » sur « Régulière », « Écarts aléatoires » ou « Asymétrique », et comparez « Sondages » avec « La recherche dichotomique demanderait ».
Fonctionnement de la recherche par interpolation
Regardez la première et la dernière valeur de la partie de la liste triée qui peut encore contenir la valeur cherchée. Si celle-ci se situe, par exemple, à 40 % du chemin entre la première valeur et la dernière, sondez la position située à 40 % de la liste. Si la valeur à cet endroit est la valeur cherchée, c'est terminé. Si elle est plus petite, il ne reste que les positions après elle ; si elle est plus grande, seulement celles avant elle. Estimez à nouveau dans ce qui reste. Si la valeur cherchée est plus petite que la première valeur ou plus grande que la dernière, elle n'y est pas.
Quand l'estimation fonctionne
Si les valeurs sont réparties régulièrement, comme 10, 20, 30 et ainsi de suite, la première estimation tombe sur la valeur cherchée ou tout près, et la recherche demande en moyenne environ log₂(log₂ n) sondages : environ 5 pour un milliard de valeurs, contre 30 pour la recherche dichotomique. Si les valeurs se regroupent, comme 1, 2, 3, 4, 1000, les estimations tombent sans cesse au mauvais endroit et chaque sondage peut n'écarter qu'une valeur : le pire cas est donc de n sondages. La recherche dichotomique ne fait jamais pire qu'environ log₂ n.
Questions fréquemment posées
Comment fonctionne la recherche par interpolation ?
Sur une liste triée, elle estime où devrait se trouver la valeur cherchée d'après la première et la dernière valeur de la partie restante, sonde cette position et ne garde que la partie du bon côté. C'est comme la recherche dichotomique, avec une estimation plus fine que le milieu.
La recherche par interpolation est-elle plus rapide que la recherche dichotomique ?
Sur des valeurs réparties régulièrement, oui : environ log₂(log₂ n) sondages en moyenne au lieu d'environ log₂ n. Sur des valeurs réparties irrégulièrement, elle peut être bien plus lente, jusqu'à n sondages, alors que la recherche dichotomique n'a jamais besoin de plus d'environ log₂ n.
Pourquoi peut-elle être lente ?
Parce que l'estimation suppose que les valeurs croissent régulièrement. Si la plupart des valeurs sont petites et quelques-unes énormes, l'estimation pour une petite valeur cherchée tombe encore et encore près du début et n'écarte qu'une ou deux valeurs à chaque fois.
Où utilise-t-on la recherche par interpolation ?
Là où les clés sont réparties de façon presque régulière et où les sondages coûtent cher, par exemple pour retrouver sur disque des enregistrements par identifiant numérique ou par hachage. Beaucoup de systèmes la combinent avec la recherche dichotomique pour garder un bon pire cas.
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