Búsqueda de Fibonacci

1. Algoritmo de búsqueda de Fibonacci
2. Ejemplo de búsqueda de Fibonacci
3. Implementación del algoritmo de búsqueda de Fibonacci
4. Complejidad del algoritmo de búsqueda de Fibonacci

La búsqueda de Fibonacci es un algoritmo de búsqueda de intervalo eficiente. Es similar a búsqueda binaria en el sentido de que también se basa en la estrategia de divide y vencerás y también necesita el array para ser ordenado. Además, la complejidad del tiempo para ambos algoritmos es logarítmica. Se llama búsqueda de Fibonacci porque utiliza la serie de Fibonacci (el número actual es la suma de dos predecesores F[i] = F[i-1] + F[i-2], F[0] = 0 y F[1]= 1 son los dos primeros números Series) y dividel array en dos partes con el tamaño dado por los números de Fibonacci. Es un método fácil de calcular que usa solo operaciones de suma y resta en comparación con la división, multiplicación y cambios de bits requeridos por la búsqueda binaria.

Algoritmo de búsqueda de Fibonacci

Supongamos que tenemos un array sin clasificar A[] que contiene n elementos, y queremos encontrar un elemento - X.

Ejemplo de búsqueda de Fibonacci

Supongamos que tenemos el array (1, 2, 3, 4, 5, 6, 7). Tenemos que buscar el elemento X = 6.

el array tiene 7 elementos. Entonces, n = 7. El número de Fibonacci más pequeño mayor que n es 8.

Implementación del algoritmo de búsqueda 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;
}

Complejidad del algoritmo de búsqueda de Fibonacci

Complejidad del tiempo

• Caso promedio

Reducimos el espacio de búsqueda en un tercio / dos tercios en cada iteración y, por lo tanto, el algoritmo tiene una complejidad logarítmica. La complejidad de tiempo del algoritmo de búsqueda de Fibonacci es O(logn).

• Mejor caso

La complejidad del tiempo en el mejor de los casos es O(1). Ocurre cuando el elemento a buscar es el primer elemento que comparamos.

• Peor caso

El peor de los casos ocurre cuando el elemento objetivo X siempre está presente en el subarreglo más grande. La complejidad de tiempo en el peor de los casos es O(logn). Es lo mismo que la complejidad del tiempo promedio de los casos.

Complejidad espacial

La complejidad espacial de este algoritmo es O(1) porque no se requiere espacio adicional más que las variables temporales.