Recherche interpolation 

Étant donné un tableau trié de n valeurs uniformément distribuées arr[], écrivez une fonction pour rechercher un élément particulier x dans le tableau. 
La recherche linéaire trouve l'élément en un temps ONon, la recherche par saut prend un temps O(√ n) et la recherche binaire prend un temps O(log n). 
La recherche par interpolation est une amélioration par rapport à la recherche binairepour les instances, où les valeurs d'un tableau trié sont uniformément distribuées. L'interpolation construit de nouveaux points de données dans la plage d'un ensemble discret de points de données connus. La recherche binaire va toujours à l'élément du milieu pour vérifier. D'autre part, la recherche par interpolation peut aller à différents emplacements en fonction de la valeur de la clé recherchée. Par exemple, si la valeur de la clé est plus proche du dernier élément, la recherche par interpolation est susceptible de commencer la recherche vers la fin.
Pour trouver la position à rechercher, il utilise la formule suivante

Il existe de nombreuses méthodes d'interpolation différentes et l'une d'elles est connue sous le nom d'interpolation linéaire. L'interpolation linéaire prend deux points de données que nous supposons être (x1,y1) et (x2,y2) et la formule est : au point (x,y).

Cet algorithme fonctionne de manière à rechercher un mot dans un dictionnaire. L'algorithme de recherche par interpolation améliore l'algorithme de recherche binaire. La formule pour trouver une valeur est : K = data-low/high-low.

K est une constante utilisée pour réduire l'espace de recherche. Dans le cas d'une recherche binaire, la valeur de cette constante est : K=(bas+haut)/2.

La formule de pos peut être dérivée comme suit.

Algorithme 
Le reste de l'algorithme d'interpolation est le même à l'exception de la logique de partition ci-dessus. 
Étape 1 : Dans une boucle, calculez la valeur de « pos » à l'aide de la formule de position de la sonde. 
Étape 2 : S'il s'agit d'une correspondance, renvoyez l'index de l'élément et quittez. 
Étape 3 : Si l'élément est inférieur à arr[pos], calculez la position de la sonde du sous-tableau gauche. Sinon, calculez la même chose dans le sous-tableau de droite. 
Étape 4 : Répétez jusqu'à ce qu'une correspondance soit trouvée ou que le sous-tableau soit réduit à zéro.
Vous trouverez ci-dessous l'implémentation de l'algorithme

int interpolationSearch(int arr[], int lo, int hi, int x)
{
    int pos;
    // Since array is sorted, an element present
    // in array must be in range defined by corner
    if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
        // Probing the position with keeping
        // uniform distribution in mind.
        pos = lo
              + (((double)(hi - lo) / (arr[hi] - arr[lo]))
                 * (x - arr[lo]));
  
        // Condition of target found
        if (arr[pos] == x)
            return pos;
  
        // If x is larger, x is in right sub array
        if (arr[pos] < x)
            return interpolationSearch(arr, pos + 1, hi, x);
  
        // If x is smaller, x is in left sub array
        if (arr[pos] > x)
            return interpolationSearch(arr, lo, pos - 1, x);
    }
    return -1;
}
  
// Driver Code
int main()
{
    // Array of items on which search will
    // be conducted.
    int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
                  22, 23, 24, 33, 35, 42, 47 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    int x = 18; // Element to be searched
    int index = interpolationSearch(arr, 0, n - 1, x);
  
    // If element was found
    if (index != -1)
        printf("Element found at index %d", index);
    else
        printf("Element not found.");
    return 0;
}
Elément trouvé à l'index 4
Modifié le: vendredi 12 août 2022, 20:32