Recherche par interpolation

La recherche par interpolation estime où se trouve une valeur cible en la comparant aux valeurs aux extrémités de l’intervalle courant. Dans des données triées dont les valeurs sont réparties assez uniformément, cette sonde fondée sur la valeur peut atteindre la cible en moins de sondes que la recherche dichotomique, qui vérifie toujours le milieu. L’estimation est moins utile lorsque les valeurs sont regroupées ou espacées de manière irrégulière : l’hypothèse sur leur répartition est donc importante. L’analogie avec un dictionnaire est parlante : pour chercher un mot commençant par « s », on l’ouvre plus près de la fin que du milieu, puis on réduit l’intervalle en fonction de ce que l’on observe.

Algorithme de recherche par interpolation

Pour un tableau A en ordre croissant et une cible X, conservez les bornes inclusives lo et hi, initialisées aux indices du premier et du dernier élément. Le tableau doit être trié ; sinon, les comparaisons avec les bornes et l’estimation de la sonde ne permettent pas d’écarter des valeurs de façon sûre. Tant que X se trouve entre A[lo] et A[hi], estimez une position à l’aide de la formule suivante :

mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])

Le calcul utilise la division entière : l’estimation est donc un indice du tableau. Si A[mid] est inférieur à X, poursuivez à partir de mid + 1 ; s’il lui est supérieur, poursuivez à partir de mid - 1 ; s’il est égal, renvoyez mid. Avant l’estimation, traitez le cas où les valeurs aux deux extrémités sont égales : si elles correspondent à X, renvoyez l’un des indices de bord ; sinon, la cible ne peut pas se trouver dans cet intervalle. Arrêtez-vous lorsque les bornes se croisent. Vous pouvez aussi rejeter immédiatement une cible située hors des valeurs aux extrémités courantes. Ces vérifications évitent une division par zéro et l’accès à un intervalle vide.

Exemple de recherche par interpolation

Considérons A = (1, 3, 7, 8, 11, 15, 17, 18, 21) et la cible X = 18. Au départ, lo = 0, hi = 8, A[lo] = 1 et A[hi] = 21. Après division entière, l’estimation vaut 0 + (18 - 1) * (8 - 0) / (21 - 1) = 6. Comme A[6] = 17 est inférieur à la cible, fixez lo = 7. La nouvelle estimation vaut 7 + (18 - 18) * (8 - 7) / (21 - 18) = 7. Puisque A[7] = 18, la recherche renvoie l’indice 7.

Implémentation de l’algorithme de recherche par interpolation

Cet exemple C++ complet utilise les mêmes valeurs et la même cible que la trace. La fonction renvoie un indice commençant à zéro si elle trouve la cible, et -1 sinon.

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

#include <iostream>
#include <limits>
#include <vector>

static_assert(std::numeric_limits<int>::digits <= 31,
              "This implementation supports int types up to 32 bits");

int interpolationSearch(const std::vector<int>& values, int target) {
    if (values.empty() ||
        values.size() > static_cast<std::size_t>(std::numeric_limits<int>::max())) {
        return -1;
    }

    int lo = 0;
    int hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi && target >= values[lo] && target <= values[hi]) {
        if (values[lo] == values[hi]) {
            return values[lo] == target ? lo : -1;
        }

        const int mid = lo + static_cast<int>(
            ((static_cast<long long>(target) - static_cast<long long>(values[lo])) *
             (hi - lo)) /
            (static_cast<long long>(values[hi]) -
             static_cast<long long>(values[lo])));

        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    const std::vector<int> values{1, 3, 7, 8, 11, 15, 17, 18, 21};
    const int target = 18;
    const int result = interpolationSearch(values, target);
    if (result >= 0) std::cout << "Element found at index " << result << '\n';
    else std::cout << "Element not found\n";
}

Element found at index 7

Les gardes couvrent un vecteur vide, une cible située hors de l’intervalle des valeurs courantes et un intervalle dont les valeurs aux extrémités sont égales. Cette implémentation exige que int ait au plus 32 bits et prend en charge les vecteurs de INT_MAX éléments au maximum ; elle vérifie la taille avant de convertir un indice en int. La conversion des deux valeurs en long long avant chaque soustraction garantit que la différence au numérateur et le dénominateur restent sûrs pour toute la plage des int sur 32 bits. Le plus grand produit possible au numérateur est (2^32 - 1) * (INT_MAX - 1) ; il tient dans un long long signé sur 64 bits. Le quotient est compris entre zéro et hi - lo, donc son addition à lo reste dans les bornes. L’entrée doit toujours être triée en ordre croissant. Le bloc de sortie conservé tel quel affiche le résultat de l’exemple ; son libellé visible reste en anglais. L’exemple est autonome et ne nécessite aucun fichier supplémentaire.

Complexité de l’algorithme de recherche par interpolation

Complexité temporelle

Le meilleur cas est O(1) : la première position estimée contient la cible. Lorsque les valeurs sont réparties à peu près uniformément dans l’intervalle trié, le temps moyen est O(log log n), car chaque estimation fondée sur les valeurs tend à réduire fortement l’intervalle. Ce résultat en moyenne dépend de cette hypothèse de répartition ; il ne garantit pas les mêmes performances pour tous les tableaux triés.

Le pire cas est O(n). Si les estimations font régulièrement peu de progrès, l’algorithme peut examiner un nombre linéaire de positions. Cela peut se produire lorsque la répartition est très irrégulière. La recherche dichotomique peut alors être un choix plus prévisible si la répartition est inconnue ou irrégulière.

Complexité spatiale

L’implémentation itérative utilise un nombre fixe de variables scalaires : son espace auxiliaire est donc O(1). Elle n’alloue pas de tableau supplémentaire et n’utilise pas la récursion.