Búsqueda por interpolación

Cuando buscas «Taylor» en una guía telefónica, no la abres por la mitad: la abres cerca del final, porque la T va tarde en el alfabeto. La búsqueda por interpolación hace lo mismo con números. Adivina dónde debería estar el valor buscado según lo grande que es, y con datos distribuidos uniformemente esa estimación es notablemente buena.

Una fila ordenada de barras con una línea de la primera a la última barra, y el sondeo situado donde la altura del valor buscado corta esa línea
Una fila ordenada de barras con una línea de la primera a la última barra, y el sondeo situado donde la altura del valor buscado corta esa línea

La idea

La búsqueda binaria siempre sondea el centro, busque lo que busque. La búsqueda por interpolación usa los valores. Si la parte que queda de la lista va de 10 a 100 y el valor buscado es 70, este está a dos tercios del camino entre el primer valor y el último, así que sondea a dos tercios de la lista. En forma de fórmula, el sondeo está en lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Tras el sondeo, se queda con la parte del lado correcto, exactamente como la búsqueda binaria, y vuelve a estimar.

Dos ejemplos

En 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, buscar 70 sondea la posición 7 directamente: encontrado en 1 sondeo, donde la búsqueda binaria necesita 4. Ahora toma 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 y busca 9. Por culpa del 999, cada estimación cae cerca del principio: la búsqueda sondea 1, 2, 3 y así sucesivamente, una posición cada vez, y necesita 9 sondeos donde la búsqueda binaria necesita 3.

Su velocidad

Cuando los valores están distribuidos uniformemente, o se extraen al azar de una distribución uniforme, cada sondeo reduce la parte que queda de unos n a unos √n. Eso da de media unos log₂(log₂ n) sondeos: unos 5 incluso para mil millones de valores, frente a 30 de la búsqueda binaria. Cuando los valores están muy mal distribuidos, un sondeo puede descartar un solo valor, y el peor caso son n sondeos, tan malo como la búsqueda lineal. Cada sondeo además cuesta una división, así que en la práctica compensa sobre todo cuando los sondeos son caros, como las lecturas de disco.

Historia y variantes

W. W. Peterson describió la búsqueda por interpolación en 1957, para encontrar registros en almacenamiento de acceso aleatorio. Su media de log log n con claves distribuidas uniformemente la demostraron en 1978 Perl, Itai y Avni. Las versiones prácticas se protegen de los datos desfavorables intercalando pasos binarios, por ejemplo la búsqueda interpolación-secuencial o interpolación-binaria, para que el peor caso se mantenga cerca de log n.

Pruébala

Abre la aplicación, elige un valor en «Buscar» y pulsa «Paso». Cada sondeo indica en qué punto está el valor buscado entre los dos valores de los extremos y a qué posición apunta eso. Pon «Distribución» en «Uniforme» y la mayoría de las búsquedas terminan en un sondeo; ponla en «Sesgada» y los sondeos avanzan despacio por el principio de la lista. El último recuadro muestra cuántos pasos necesitaría la búsqueda binaria para el mismo valor.

Preguntas frecuentes

¿Cuál es la complejidad temporal de la búsqueda por interpolación?

O(log log n) de media con valores distribuidos uniformemente, y O(n) en el peor caso. Necesita O(1) de memoria adicional y una lista ordenada.

¿Qué diferencia hay entre la búsqueda por interpolación y la búsqueda binaria?

La búsqueda binaria siempre sondea el centro de lo que queda. La búsqueda por interpolación sondea donde debería estar el valor buscado, a juzgar por los valores de los dos extremos. Eso es mucho mejor con valores distribuidos uniformemente y puede ser mucho peor con valores sesgados.

¿Qué datos son adecuados para la búsqueda por interpolación?

Claves numéricas ordenadas que estén distribuidas de forma bastante uniforme: ID secuenciales con pocos huecos, marcas de tiempo de eventos regulares o claves hash. Encaja con datos en los que un sondeo es caro y un poco de aritmética es barata.

¿Por qué la aplicación ofrece distintas distribuciones?

Porque la distribución decide lo buenas que son las estimaciones. Con valores uniformes, la búsqueda por interpolación parece casi mágica, y los valores sesgados muestran su debilidad. Compararlos con el recuento de la búsqueda binaria es la forma más clara de ver cuándo usar cada una.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Prueba la búsqueda por interpolación