Recherche Fibonacci

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

La recherche de Fibonacci est un algorithme de recherche par intervalle efficace. Elle est similaire à la [Recherche dichotomique](/fr/tutorial/algorithm/binary-search/ dans le sens où elle est également basée sur la stratégie diviser pour mieux régner et qu’elle a également besoin du tableau pour être triée. De plus, la complexité temporelle des deux algorithmes est logarithmique. Il est appelé recherche de Fibonacci car il utilise la série de Fibonacci (Le nombre actuel est la somme de deux prédécesseurs F[i] = F[i-1] + F[i-2], F[0]=0 & F[1]=1 sont les deux premiers nombres de la série.) et divise le tableau en deux parties dont la taille est donnée par les nombres de Fibonacci. Il s’agit d’une méthode de calcul conviviale qui n’utilise que des opérations d’addition et de soustraction par rapport à la division, la multiplication et les décalages de bits requis par la Recherche dichotomique.

Algorithme de recherche de Fibonacci

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

Exemple de recherche Fibonacci

Supposons que nous ayons le tableau : (1, 2, 3, 4, 5, 6, 7). Nous devons chercher l’élément X = 6.

Le tableau a 7 éléments. Le plus petit nombre de Fibonacci supérieur à n est 8.

Mise en œuvre de l’algorithme de recherche de Fibonacci

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

int fibonacciSearch(int A[], int x, int n) {
  int fbM2 = 0;
  int fbM1 = 1;
  int fbM = fbM2 + fbM1;
  int offset = -1;
  while (fbM < n) {
    fbM2 = fbM1;
    fbM1 = fbM;
    fbM = fbM2 + fbM1;
  }
  while (fbM > 1) {
    int i = min(offset + fbM2, n - 1);
    if (A[i] < x) {
      fbM = fbM1;
      fbM1 = fbM2;
      fbM2 = fbM - fbM1;
      offset = i;
    } else if (A[i] > x) {
      fbM = fbM2;
      fbM1 = fbM1 - fbM2;
      fbM2 = fbM - fbM1;
    } else
      return i;
  }
  if (fbM1 && A[offset + 1] == x) return offset + 1;

  return -1;
}

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

Complexité de l’algorithme de recherche de Fibonacci

Complexité du temps

• Cas moyen

Nous réduisons l’espace de recherche d’un tiers / deux tiers à chaque itération, et l’algorithme a donc une complexité logarithmique. La complexité temporelle de l’algorithme de recherche de Fibonacci est O(logn).

• Meilleur cas

Le meilleur cas de complexité temporelle est O(1). Elle se produit lorsque l’élément à rechercher est le premier élément que nous comparons.

• Pire cas

Le pire cas se produit lorsque l’élément cible X est toujours présent dans le grand sous-réseau. La complexité temporelle la plus défavorable est O(logn). C’est la même chose que la complexité temporelle moyenne.

Complexité spatiale

La complexité spatiale de cet algorithme est O(1) car aucun espace supplémentaire autre que des variables temporaires n’est nécessaire.