¿La búsqueda de sección dorada es mejor que la búsqueda binaria?

Question

Recientemente he escuchado una opinión de que la búsqueda binaria puede mejorarse dividiendo el rango por phi (ración dorada) en lugar de por 2. Esto fue una gran sorpresa para mí, porque nunca escuché acerca de dicha optimización. ¿Es esto cierto? ¿Hubiera sido esto cierto si la división por 2 y por phi fuera igualmente efectiva?

En caso negativo, ¿hay alguna condición general en virtud de la cual la búsqueda de sección dorada se realice más rápido que la búsqueda binaria?

UPD: Editado para eliminar el enlace a un artículo de Wikipedia no relevante. Lo siento por ser engañoso.

Answer 1

Hay dos algoritmos llamados "búsqueda de Fibonacci".

es sobre un algoritmo numérico para encontrar el máximo o mínimo de ciertas funciones. Es el algoritmo óptimo para este problema. Este problema es lo suficientemente diferente del problema de búsqueda binaria que debería ser obvio para cualquier caso dado que sea apropiado.

The other kind of Fibonacci search ataca el mismo problema que la búsqueda binaria. La búsqueda binaria es esencialmente siempre mejor. Knuth escribe que la búsqueda de Fibonacci "es preferible en algunas computadoras, porque implica solo sumas y restas, no división por 2." Pero casi todas las computadoras usan aritmética binaria, en la que la división por 2 es más simple que la suma y la resta.

(El artículo de Wikipedia afirma actualmente que Fibonacci búsqueda podría tener mejor localidad de referencia, una reclamación Knuth hace no maquillaje. Se podría, tal vez, pero esto es engañoso. Las pruebas realizadas por una búsqueda de Fibonacci están más cerca Juntos, precisamente en la medida en que son menos útiles para reducir el rango, en promedio esto daría como resultado más lecturas de más partes de la tabla, no menos. Si los registros se almacenan realmente en cinta, para que domine el tiempo de búsqueda, entonces La búsqueda de Fibonacci puede superar la búsqueda binaria —, pero en ese caso ambos algoritmos están lejos de ser óptimos.)

Answer 2

"funciona más rápido" es vago; pero la búsqueda binaria debe tener el peor caso más bajo vinculado al número de accesos.

Answer 3

Me puede faltar algo aquí, pero después de mirar la entrada de Wikipedia en la sección de búsqueda dorada parece que no resuelve el mismo problema que una búsqueda binaria. Mientras que una búsqueda binaria es útil para encontrar un valor en una lista ordenada, se utiliza una búsqueda de sección dorada para encontrar un valor mínimo o máximo de una función en un rango de valores.