Recherche par interpolation

1. Algorithme de recherche par interpolation
2. Exemple de recherche par interpolation
3. Mise en œuvre de l’algorithme de recherche par interpolation
4. Complexité de l’algorithme de recherche par interpolation

La recherche par interpolation est un algorithme de recherche rapide et efficace. Il améliore l’algorithme de recherche dichotomique pour les scénarios où les éléments du tableau sont uniformément répartis sur le tableau trié. Il travaille sur la position de sondage de la valeur requise. Contrairement à la recherche dichotomique, elle ne va pas toujours au milieu du tableau mais peut aller à n’importe quelle position en fonction de la valeur de la clé à rechercher. Nous comparons la valeur à la position estimée et réduisons l’espace de recherche à la partie qui la suit ou la précède. Par exemple, lorsque nous recherchons un mot dans le dictionnaire, nous retournons les pages en fonction de la position des lettres à l’intérieur de celui-ci et non en divisant chaque fois l’espace de recherche en deux moitiés.

Algorithme de recherche par interpolation

Supposons que nous ayons un tableau non trié A[] contenant n éléments et que nous voulons trouver un élément donné X.

Exemple de recherche par interpolation

Supposons que nous ayons le tableau : (1, 3, 7, 8, 11, 15, 17, 18, 21), et que nous voulions trouver X - 18.

Mise en œuvre de l’algorithme de recherche par interpolation

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X) {
  int lo = 0;
  int hi = n - 1;
  int mid;

  while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
    mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

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

  if (X == arr[lo])
    return lo;
  else
    return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int result = interpolation_search(arr, n, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Complexité de l’algorithme de recherche par interpolation

Complexité du temps

• Cas moyen

La complexité temporelle moyenne de l’algorithme est de l’ordre de O(log(logn)). Elle se produit lorsque tous les éléments à l’intérieur du tableau sont uniformément distribués.

• Meilleur cas

Le meilleur cas se produit lorsque l’élément que nous recherchons est le premier élément interrogé par la recherche par interpolation. Le meilleur cas de complexité temporelle de l’algorithme est O(1).

• Le pire cas

Le pire cas se produit lorsque les valeurs numériques des cibles augmentent de manière exponentielle. La complexité temporelle de l’algorithme dans le pire des cas est O(n).

Complexité spatiale

La complexité spatiale de cet algorithme est O(1) car il ne nécessite aucune structure de données autre que des variables temporaires.