Recherche exponentielle

Harshit Jindal 12 octobre 2023
  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
Recherche exponentielle
Note
Si vous ne savez pas ce qu’est la Recherche dichotomique, veuillez d’abord passer par le [algorithme de Recherche dichotomique](/fr/tutorial/algorithm/binary-search/ ici.

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.

  • Vérifiez si le premier élément lui-même est l’élément cible, c’est-à-dire A[0] == X.
  • Initialisez i comme 1.
  • Alors que i < n et A[i] <= X, faites ce qui suit :
    • Augmentez i en puissances de 2 c’est-à-dire i = i*2.
  • Appliquer la Recherche dichotomique sur la plage de i/2 à min(i,n-1).

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.

  • Initialiser i en tant que 1
  • A[1] = 2 < 10 donc incrémenter i à 2.
  • A[2] = 3 < 10 donc incrémenter i à 4.
  • A[4] = 5 < 10 donc incrémenter i à 8.
  • A[8] = 9 < 10 donc incrémenter i à 16.
  • i = 16 > n D’où l’appel à la Recherche dichotomique sur la plage i/2 c’est-à-dire 8 à min(i,n-1) c’est-à-dire min(16,10) =10.
  • Initialisez lo comme i / 2 = 8 et hi comme min(i, n-1) = 10.
  • calculer mid comme 9.
  • 10 == 10 c’est-à-dire A[9] == X, donc renvoyer 9.

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)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.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Article connexe - Search Algorithm