Acabo de leer ¿Puede este algoritmo seguir considerándose un algoritmo de búsqueda binaria? y recordé que hace unos años escribí un indexador / búsqueda de archivos de registro para encontrar entradas de registro en grandes archivos de texto sin formato por ventana de fecha / hora.
Mientras hacía esto, decidí probar la búsqueda de interpolación (no sabía cómo se llamaba, me tropecé con la idea por mí mismo). Luego, por alguna razón, continué con la idea de alternar los pasos de interpolación con los pasos binarios divididos: en el paso 0, interpolaría para decidir el punto de prueba, luego, en el paso 1, tomaría el punto medio exacto, etc.
Luego comparé el sistema con la búsqueda de interpolación pura, la búsqueda binaria pura y mi intento de combinación. El enfoque alternativo fue un claro ganador, tanto en tiempo como en número de pruebas requeridas antes de encontrar un conjunto de tiempos elegidos al azar.
Inspirado por la pregunta vinculada, hice una búsqueda rápida de "búsqueda de interpolación alterna y búsqueda binaria" y no encontré nada. También probé la "búsqueda de interpolación cubierta" como se sugiere en mi comentario sobre una de las respuestas.
¿Me he tropezado con algo conocido? ¿Existe alguna justificación teórica para que sea más rápido para ciertos tipos de datos? Los archivos de registro eran generalmente grandes para la época (por ejemplo, 1-2 GB de texto con quizás 10 millones de filas para buscar), y la propagación de fechas / horas en ellos era compleja con fuertes estallidos de actividad, horas pico generales y tiempos de silencio. Mis pruebas de referencia tomaron muestras de una distribución uniforme de tiempos objetivo para encontrar.
fuente
prefetcht0
instrucciones ) ambas posibilidades para la iteración NEXT antes de cargar el punto medio actual, para una búsqueda en memoria en el hardware moderno x86. No puede hacer eso si no puede predecir las próximas direcciones de búsqueda con anticipación. Por lo tanto, los detalles prácticos de implementación pueden ser significativos, aparte de las consideraciones teóricas .