Recherche d'interpolation vs recherche binaire

Quand dois-je utiliser la recherche par interpolation au lieu de la recherche binaire?

Par exemple, j'ai un ensemble de données trié, dans quelles situations devrais-je utiliser la recherche binaire pour trouver un élément dans cet ensemble de données ou dans quelle situation dois-je utiliser la recherche par interpolation?

Quelles propriétés de l'ensemble de données seraient le facteur déterminant?

Évidemment, pour faire une recherche par interpolation, vous avez besoin d'un type de clé pour lequel plus que la commande est connue - vous devez être en mesure de faire des calculs sur les clés pour estimer une distance probable, pas seulement comparer les clés pour déterminer laquelle est plus grande ou moindre.

En ce qui concerne les propriétés de l'ensemble de données, il s'agit principalement d'une propriété: la probabilité que les clés soient réparties de manière raisonnablement uniforme (ou du moins prévisible) dans toute la gamme des possibilités. Sans cela, une recherche par interpolation peut en fait être plus lente qu'une recherche binaire.

Par exemple, considérons un ensemble de données avec des chaînes de lettres minuscules comme clés. Supposons que vous ayez une clé qui commence par "x". Une recherche par interpolation indiquera clairement que vous devriez commencer la recherche très près de la fin de l'ensemble. Si, cependant, la plupart de vos clés commencent réellement par 'z', et quasiment aucune avec quoi que ce soit de 'a' à 'y', celle que vous recherchez peut en fait être très proche du début de l'ensemble. Cela peut / peut prendre un nombre considérable d'itérations avant que la recherche ne se rapproche du début où réside la chaîne commençant par «w». Chaque itération ne supprimerait que ~ 10% de l'ensemble de données de la prise en compte, il faudrait donc plusieurs itérations avant de se rapprocher du début où les clés commençant par «w»

En revanche, une recherche binaire commencerait au milieu, atteindrait la marque d'un quart à la deuxième itération, une huitième à la troisième, et ainsi de suite. Ses performances ne seraient presque pas affectées par l'inclinaison des touches. Chaque itération supprimerait la moitié de l'ensemble de données de la considération, comme si les clés étaient réparties uniformément.

Je m'empresse d'ajouter, cependant, qu'il faut vraiment une distribution assez asymétrique pour rendre une recherche d'interpolation sensiblement pire qu'une recherche binaire. Il peut, par exemple, fonctionner assez bien même en présence d'une bonne quantité de clustering localisé.

Je dois également mentionner qu'une recherche par interpolation n'a pas nécessairement besoin d'utiliser une interpolation linéaire. Par exemple, si vos clés sont connues pour suivre une distribution non linéaire (par exemple, une courbe en cloche), il devient assez facile de prendre cela en compte dans la fonction d'interpolation pour obtenir des résultats peu différents d'avoir une distribution uniforme.

Je pense probablement que la question est de savoir avec quelle facilité vous pouvez trouver une fonction d'interpolation qui fait en fait mieux que la recherche binaire.

De Wikipedia sur la recherche d'interpolation:

En utilisant la notation big-O, la performance de l'algorithme d'interpolation sur un ensemble de données de taille N est O (N); cependant, dans l'hypothèse d'une distribution uniforme des données sur l'échelle linéaire utilisée pour l'interpolation, la performance peut être montrée comme O (log log N).

Les performances pratiques de la recherche par interpolation dépendent du fait que le nombre réduit de sondes est compensé par les calculs plus compliqués nécessaires pour chaque sonde. Il peut être utile pour localiser un enregistrement dans un grand fichier trié sur le disque, où chaque sonde implique une recherche de disque et est beaucoup plus lente que l'arithmétique d'interpolation.

Les structures d'index comme les arbres B réduisent également le nombre d'accès au disque et sont plus souvent utilisées pour indexer les données sur le disque en partie car elles peuvent indexer de nombreux types de données et peuvent être mises à jour en ligne. Pourtant, la recherche par interpolation peut être utile lorsque l'on est obligé de rechercher certains ensembles de données sur disque triés mais non indexés.

La recherche binaire et la recherche par interpolation sont toutes deux considérées comme des méthodes de recherche linéaire.

Ils s'attendent tous les deux à ce que la liste recherchée soit triée dans la colonne appelée clé . C'est très important.

La recherche binaire fonctionne pour les chaînes ou les nombres tant qu'ils sont stockés dans un ordre trié. L'idée principale derrière la recherche binaire est qu'elle est basée sur l'examen de l'élément central. La recherche par interpolation est une variante. Au lieu d'utiliser l'élément central exact, il devine où se trouve l'élément suivant à comparer avec la valeur transmise. Voir la référence fournie par la réponse de JB King ou celle ci-dessous dans cette réponse pour plus de détails sur la façon dont l'algorithme de recherche d'interpolation calcule la valeur de clé suivante.

"La recherche par interpolation ne fonctionne que sur les éléments numériques disposés dans l'ordre des tableaux triés avec une distribution uniforme (c'est-à-dire que l'intervalle entre l'un quelconque des éléments successifs est à peu près constant" (citation de la référence ci-dessous P 737, une comparaison des performances entre les différentes méthodes de recherche linéaire est également incluse) ).

Google Livres - Classic Data Structures 2Nd Ed.