Recherche par interpolation

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Interpolation.

La recherche par interpolation est un algorithme de recherche dans un tableau trié.

Principe[modifier | modifier le code]

Le principe est similaire à celui de la recherche dichotomique : il s'agit de comparer un élément du tableau avec la valeur recherchée, puis de rechercher récursivement dans la portion du tableau pertinente. La différence est sur le choix de la valeur du tableau choisit. Dans une recherche dichotomique c'est la médiane qui est utilisée. Ce choix n'est pas optimal si l'on sait que les valeurs sont « bien reparties », par exemple pour rechercher le mot «banane» dans un dictionnaire, il est plus pertinent de chercher au début du dictionnaire. Ainsi dans la recherche par interpolation, c'est la position qui correspond à la place de l'élément cherché, si les données étaient régulièrement espacées entre le minimum et le maximum du (sous-)tableau, qui est étudiée[1].

Complexité[modifier | modifier le code]

Si les valeurs du tableau sont tirées selon la loi uniforme, alors la recherche a une complexité en temps en moyenne de [1],[2].

Histoire[modifier | modifier le code]

L'algorithme a été présenté par W Wesley Peterson[3], dans un article de 1957[4].

Notes et références[modifier | modifier le code]

  1. a et b « Algorithmes de recherche de base », sur EPITA.
  2. Yehoshua Perl, Alon Itai et Haim Avni, « Interpolation search—a log log N search », Communications of the ACM, vol. 21, no 7,‎ , p. 550-553
  3. Andersson, Arne and Mattsson, Christer, « Dynamic Interpolation Search in o (log log n) Time », Automata, Languages and Programming,‎ , p. 15-27
  4. W Wesley Peterson, « Addressing for random-access storage », IBM journal of Research and Development, vol. 1, no 2,‎ , p. 130-146.

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Lien externe[modifier | modifier le code]