Técnica de búsqueda de Fibonacci

En ciencia de la computación, la técnica de búsqueda de Fibonacci es un método de búsqueda en un array ordenado usando un algoritmo de divide y vencerás que disminuye las ubicaciones posibles con la ayuda de los números de Fibonacci. Comparado con la búsqueda binaria, Fibonacci busca las ubicaciones cuyas direcciones tienen poca dispersión. Por lo tanto, cuando los elementos se buscan, tiene un acceso a memoria no uniforme (el tiempo necesario para acceder a la ubicación de almacenamiento varía en dependencia de la ubicación previamente accedida), la búsqueda de Fibonacci tiene una ventaja sobre la búsqueda binaria en disminuir ligeramente el tiempo promedio necesario para acceder a la ubicación de almacenamiento. El típico ejemplo de acceso no uniforme al almacenamiento es una cinta magnética, donde el tiempo de acceso a un elemento en particular es proporcional a su distancia desde el elemento actual apuntado por el cabezal de la cinta. Note, sin embargo, que grandes arrays no adecuados en la caché del CPU o incluso en RAM pueden ser considerados como ejemplos de acceso no uniforme. La búsqueda de Fibonacci tiene complejidad O(log(x)) (Ver notación de O Grande). La búsqueda de Fibonacci fue concebida por primera vez por Kiefer(1953) como una búsqueda minimax para el máximo (mínimo) de una función unimodal en un intervalo.

Algoritmo

Dado un array ordenado A y un elemento t, verificar si t esta en A:
Sea F el array de los números de Fibonacci. F_m es el m-ésimo elemento de F. n es el tamaño A. Sea m tal que F_m es el número más pequeño de F mayor o igual que n.
F es definido como: F₀ = 1, F₁ = 1, F_k = F_k-1   F_k-2.

Para probar si t pertenece a A, seguir los siguientes pasos:

1. Sea k = m.

2. Si k = 0, parar. Si no machean, entonces t no esto en A.

3. Comparar t con el elemento de A en la posición F_k-1.

4. Si son iguales, entonces t esta en A.

5. Si t es menor, entonces descartar los elementos de A desde la posición F_k-1 1 hasta n.

  hacer k = k-1 y volver al paso 2.

6. Si t es mayor, entonces descartar los elementos de A desde la posición 1 hasta F_k-1.

  Renumerar los elementos restantes de A, hacer k = k - 2 y volver al paso 2.

Implementación alternativa (de "Sorting and Searching" por Knuth): Dado una tabla de registros R₁, R₂, ..., R_n cuyas llaves estón en orden incremental K₁ < K₂ < ... < K_n, el algoritmo busca por un elemento K dado. Asumir n 1 = F_{k 1}.

Paso 1. [Inicialización] i ← F_k, p ← F_k-1, q ← F_k-2 (durante el algoritmo, p y q serán números de Fibonacci consecutivos).

Paso 2. [Comparar] SI K < K_i, ir al paso 3; si K > K_i ir al paso 4; y si K = K_i, el algoritmo termina exitosamente.

Paso 3. [Decrementar i] Si q = 0, el algoritmo termina exitosamente. En otro caso set (i, p, q) ← (i - q, q, p - q) ( el cual mueve p y q una posición atrás en la secuencia de Fibonacci); luego ir al paso 2.

Paso 4. [Incrementa i] Si p = 1, el algoritmo termina exitosamente. En otro caso set (i,p,q) ← (i p, p ← p - q, q ← 2q - p) ( el cual mueve p y q dos posiciones atrás en la secuencia de Fibonacci); luego ir al paso 2.

Véase también

Referencias

 * J. Kiefer, "Sequential minimax search for a maximum", Froc. American

Mathematical Society, 1953.

David E. Ferguson, "Fibonaccian searching", Communications of the

ACM, vol. 3, is. 12, p. 648, Dec. 1960.

Manolis Lourakis, "Fibonaccian search in C".

[1]. Retrieved January 18, 2007. Implements Ferguson's algorithm.

Donald E. Knuth, "The Art of Computer Programming (second edition)",

vol. 3, p. 418, Nov. 2003.

Datos: Q4925741