¿Cuál es la lógica de la búsqueda de Fibonacci?

La búsqueda de Fibonacci es una técnica basada en la comparación que utiliza números de Fibonacci para buscar un elemento en una matriz ordenada.

Similitudes con la búsqueda binaria:

1. Funciona para arreglos ordenados
2. Un algoritmo de división y conquista.
3. Tiene Log n complejidad de tiempo.

Diferencias con la búsqueda binaria :

• ¿Cuáles son los algoritmos que uno debería usar para generar automáticamente intentos de chatbots?
• ¿Cómo funciona el algoritmo de adsorción?
• ¿Cuáles son las diferencias entre DFS y BFS?
• ¿Qué es el algoritmo de YouTube?
• Agregue dos números en la hoja1, luego vea mi respuesta en la hoja2. ¿Cómo hago eso en Excel?

1. La búsqueda de Fibonacci divide la matriz dada en partes desiguales
2. La búsqueda binaria utiliza el operador de división para dividir el rango. Fibonacci Search no usa /, pero usa + y -. El operador de división puede ser costoso en algunas CPU.
3. La búsqueda de Fibonacci examina elementos relativamente más cercanos en pasos posteriores. Entonces, cuando la matriz de entrada es grande que no puede caber en el caché de la CPU o incluso en la RAM, la búsqueda de Fibonacci puede ser útil
4. Algoritmo
5. Deje que el elemento buscado sea x.

La idea es encontrar primero el número de Fibonacci más pequeño que sea mayor o igual que la longitud de una matriz dada. Deje que el número de Fibonacci encontrado sea fib (número de fibonacci número m). Utilizamos (m-2) ‘th número de Fibonacci como índice (si es un índice válido). Sea (m-2) ‘th Número de Fibonacci ser i, comparamos arr [i] con x, si x es igual, devolvemos i. De lo contrario, si x es mayor, recurrimos para la submatriz después de i, de lo contrario, recurrimos para la submatriz antes de i.

A continuación se muestra el algoritmo completo
Deje que arr [0..n-1] sea la matriz de entrada y el elemento a buscar sea x.

1. Encuentre el número de Fibonacci más pequeño mayor o igual que n. Deje que este número sea fibM [m’th número de Fibonacci]. Deje que los dos números de Fibonacci que lo preceden sean fibMm1 [(m-1) ‘th Número de Fibonacci y fibMm2 [(m-2)’ th Número de Fibonacci./li>
2. Si bien la matriz tiene elementos que deben inspeccionarse: Compare x con el último elemento del rango cubierto por fibMm2 Si x coincide, devuelva el índice Else Si x es menor que el elemento, mueva las tres variables de Fibonacci dos Fibonacci hacia abajo, lo que indica la eliminación de aproximadamente la parte posterior dos tercios de la matriz restante. De lo contrario, x es mayor que el elemento, mueva las tres variables de Fibonacci una Fibonacci hacia abajo. Restablecer desplazamiento al índice. Juntos, estos indican la eliminación de aproximadamente un tercio frontal de la matriz restante.
3. Como puede haber un solo elemento restante para la comparación, verifique si fibMm1 es 1. En caso afirmativo, compare x con ese elemento restante. Si coincide, devuelva el índice