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 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.
Si t es menor, entonces descartar los elementos de A desde la posición Fk-1 + 1 hasta n. 6.
Si t es mayor, entonces descartar los elementos de A desde la posición 1 hasta Fk-1.
Implementación alternativa (de "Sorting and Searching" por Knuth): Dado una tabla de registros R1, R2, ..., Rn cuyas llaves estón en orden incremental K1 < K2 < ... < Kn, el algoritmo busca por un elemento K dado.