Recherche exponentielle

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

La recherche exponentielle, également connue sous le nom de recherche double ou de recherche digitale, est un algorithme créé pour rechercher des éléments dans des tableaux de taille énorme. Il s’agit d’un processus en deux étapes. Tout d’abord, l’algorithme tente de trouver la plage (L, R) dans laquelle l’élément cible est présent, puis utilise la Recherche dichotomique à l’intérieur de cette plage pour trouver l’emplacement exact de la cible.

Elle est appelée recherche exponentielle parce qu’elle trouve l’élément de maintien de la distance en recherchant le premier exposant k pour lequel l’élément à l’index pow(2, k) est plus grand que la cible. Bien que son nom soit recherche exponentielle, la complexité temporelle de cet algorithme est logarithmique. Il est très utile lorsque les tableaux sont de taille infinie et convergent vers une solution beaucoup plus rapidement que la Recherche dichotomique.

Algorithme de recherche exponentielle

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

Exemple de recherche exponentielle

Supposons que nous ayons le tableau : (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), et que nous voulions trouver X - 10.

Mise en œuvre de l’algorithme de recherche exponentielle

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

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int exponentialSearch(int arr[], int n, int x) {
  if (arr[0] == x) return 0;
  int i = 1;
  while (i < n && arr[i] <= x) i = i * 2;

  return binarySearch(arr, i / 2, min(i, n - 1), x);
}

int main() {
  int n = 11;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
  int x = 10;
  int result = exponentialSearch(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 exponentielle

Complexité temporelle

• Cas moyen

La complexité temporelle moyenne est O(logi) où i est l’indice de l’élément cible X à l’intérieur du tableau. Il surpasse même la Recherche dichotomique lorsque l’élément est proche du début du tableau.

• Meilleur cas

Le meilleur cas se produit lorsque l’élément que nous comparons est celui que nous recherchons et qu’il est renvoyé à la première itération. Le meilleur cas de complexité temporelle est O(1).

• Pire cas

La complexité temporelle du pire cas est la même que la complexité temporelle moyenne. Le pire cas de complexité temporelle est le O(logi).

Complexité spatiale

La complexité spatiale de cet algorithme est O(1) car il ne nécessite pas d’espace supplémentaire autre que des variables temporaires.