Recherche par interpolation
Quand vous cherchez « Taylor » dans un annuaire, vous ne l'ouvrez pas au milieu : vous l'ouvrez vers la fin, car le T arrive tard dans l'alphabet. La recherche par interpolation fait de même avec des nombres. Elle devine où devrait se trouver la valeur cherchée d'après sa taille, et sur des données réparties régulièrement, cette estimation est remarquablement bonne.
L'idée
La recherche dichotomique sonde toujours le milieu, quoi qu'elle cherche. La recherche par interpolation utilise les valeurs. Si la partie restante de la liste va de 10 à 100 et que la valeur cherchée est 70, celle-ci se situe aux deux tiers du chemin entre la première valeur et la dernière : on sonde donc aux deux tiers de la liste. En formule, le sondage se fait en lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Après le sondage, on garde la partie du bon côté, exactement comme dans la recherche dichotomique, et on estime à nouveau.
Deux exemples
Dans 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, la recherche de 70 sonde tout de suite la position 7 : trouvé en 1 sondage, là où la recherche dichotomique en demande 4. Prenez maintenant 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 et cherchez 9. À cause du 999, chaque estimation tombe près du début : la recherche sonde 1, 2, 3 et ainsi de suite, une position à la fois, et demande 9 sondages là où la recherche dichotomique en demande 3.
Sa rapidité
Quand les valeurs sont réparties régulièrement, ou tirées au hasard selon une distribution uniforme, chaque sondage réduit la partie restante d'environ n à environ √n. Cela donne en moyenne environ log₂(log₂ n) sondages : environ 5 même pour un milliard de valeurs, contre 30 pour la recherche dichotomique. Quand les valeurs sont très irrégulièrement réparties, un sondage peut n'écarter qu'une seule valeur, et le pire cas est de n sondages, aussi mauvais que la recherche linéaire. Chaque sondage coûte aussi une division ; en pratique, elle est donc surtout rentable quand les sondages coûtent cher, comme des lectures sur disque.
Histoire et variantes
W. W. Peterson a décrit la recherche par interpolation en 1957, pour retrouver des enregistrements sur une mémoire à accès direct. Sa moyenne en log log n pour des clés réparties régulièrement a été démontrée en 1978 par Perl, Itai et Avni. Les versions pratiques se protègent des données défavorables en intercalant des étapes dichotomiques, par exemple la recherche interpolation-séquentielle ou interpolation-dichotomique, afin que le pire cas reste proche de log n.
À vous d'essayer
Ouvrez l'application, choisissez une valeur dans « Rechercher » et appuyez sur « Étape ». Chaque sondage indique où se situe la valeur cherchée entre les deux valeurs extrêmes et vers quelle position cela pointe. Réglez « Répartition » sur « Régulière » et la plupart des recherches se terminent en un sondage ; réglez-la sur « Asymétrique » et les sondages avancent lentement au début de la liste. La dernière tuile indique combien d'étapes la recherche dichotomique demanderait pour la même valeur.
Questions fréquemment posées
Quelle est la complexité de la recherche par interpolation ?
O(log log n) en moyenne pour des valeurs réparties régulièrement, et O(n) dans le pire cas. Elle demande O(1) de mémoire supplémentaire et une liste triée.
Quelle est la différence entre la recherche par interpolation et la recherche dichotomique ?
La recherche dichotomique sonde toujours le milieu de ce qui reste. La recherche par interpolation sonde là où la valeur cherchée devrait se trouver, d'après les valeurs aux deux extrémités. C'est bien meilleur sur des valeurs réparties régulièrement, et cela peut être bien pire sur des valeurs asymétriques.
Quelles données conviennent à la recherche par interpolation ?
Des clés numériques triées et réparties assez régulièrement : des identifiants séquentiels avec peu de trous, les horodatages d'événements réguliers ou des clés hachées. Elle convient aux données pour lesquelles un sondage coûte cher et un peu de calcul presque rien.
Pourquoi l'application propose-t-elle plusieurs répartitions ?
Parce que la répartition détermine la qualité des estimations. Avec des valeurs régulières, la recherche par interpolation semble presque magique ; avec des valeurs asymétriques, sa faiblesse apparaît. Les comparer au compte de la recherche dichotomique est le moyen le plus clair de voir quand utiliser l'une ou l'autre.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer la recherche par interpolation