Recherche d'interpolation en Java

1. Introduction

Dans ce didacticiel, nous allons parcourir les algorithmes de recherche par interpolation et discuter de leurs avantages et inconvénients. De plus, nous allons l'implémenter en Java et parler de la complexité temporelle de l'algorithme.

2. Motivation

La recherche par interpolation est une amélioration par rapport à la recherche binaire conçue pour des données uniformément réparties.

La recherche binaire divise par deux l'espace de recherche à chaque étape, quelle que soit la distribution des données, donc sa complexité temporelle est toujours O (log (n)) .

D'autre part, la complexité du temps de recherche par interpolation varie en fonction de la distribution des données . C'est plus rapide que la recherche binaire de données uniformément distribuées avec la complexité temporelle de O (log (log (n))) . Cependant, dans le pire des cas, il peut être aussi mauvais que O (n) .

3. Recherche par interpolation

Semblable à la recherche binaire, la recherche par interpolation ne peut fonctionner que sur un tableau trié. Il place une sonde dans une position calculée à chaque itération. Si la sonde est juste sur l'article que nous recherchons, la position sera retournée; sinon, l'espace de recherche sera limité au côté droit ou gauche de la sonde.

Le calcul de la position de la sonde est la seule différence entre la recherche binaire et la recherche par interpolation.

Dans la recherche binaire, la position de la sonde est toujours l'élément le plus au milieu de l'espace de recherche restant.

Au contraire, la recherche par interpolation calcule la position de la sonde sur la base de cette formule:

Jetons un coup d'œil à chacun des termes:

  • sonde : la nouvelle position de la sonde sera affectée à ce paramètre.
  • lowEnd : l'index de l'élément le plus à gauche dans l'espace de recherche actuel.
  • highEnd : l'index de l'élément le plus à droite dans l'espace de recherche actuel.
  • data [] : le tableau contenant l'espace de recherche d'origine.
  • item : l'article que nous recherchons.

Pour mieux comprendre le fonctionnement de la recherche par interpolation, démontrons-le avec un exemple.

Disons que nous voulons trouver la position de 84 dans le tableau ci-dessous:

La longueur du tableau est de 8, donc initialement highEnd = 7 et lowEnd = 0 (car l'index du tableau commence à 0 et non à 1).

Dans la première étape, la formule de position de la sonde aboutira à sonde = 5:

Étant donné que 84 (l' élément que nous recherchons) est supérieur à 73 (l' élément de position actuelle de la sonde ), l'étape suivante abandonnera le côté gauche du tableau en attribuant lowEnd = sonde + 1. Maintenant, l'espace de recherche ne comprend que 84 et 101. La formule de position de la sonde définira la sonde = 6 qui est exactement l'indice 84:

Puisque l'article recherché est trouvé, la position 6 sera retournée.

4. Implémentation en Java

Maintenant que nous avons compris comment fonctionne l'algorithme, implémentons-le en Java.

Tout d'abord, nous initialisons lowEnd et highEnd :

int highEnd = (data.length - 1); int lowEnd = 0;

Ensuite, nous mettons en place une boucle et à chaque itération, nous calculons la nouvelle sonde en fonction de la formule susmentionnée. La condition de boucle garantit que nous ne sommes pas hors de l'espace de recherche en comparant l' élément aux données [lowEnd] et aux données [highEnd] :

while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); }

Nous vérifions également si nous avons trouvé l'élément après chaque nouvelle affectation de sonde .

Enfin, nous ajustons lowEnd ou highEnd pour diminuer l'espace de recherche à chaque itération:

public int interpolationSearch(int[] data, int item) { int highEnd = (data.length - 1); int lowEnd = 0; while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); if (highEnd == lowEnd) { if (data[lowEnd] == item) { return lowEnd; } else { return -1; } } if (data[probe] == item) { return probe; } if (data[probe] < item) { lowEnd = probe + 1; } else { highEnd = probe - 1; } } return -1; }

5. Conclusion

Dans cet article, nous avons exploré la recherche d'interpolation avec un exemple. Nous l'avons également implémenté en Java.

Les exemples présentés dans ce didacticiel sont disponibles à l'adresse over sur Github.