Sondeos
Aún posibles
La búsqueda binaria necesitaría

  • Valor buscado
  • Aún posibles
  • Comparadas
  • Descartadas
  • Encontradas

Más sobre la búsqueda por interpolación

Búsqueda por interpolación

La búsqueda por interpolación busca un valor en una lista ordenada como cuando abres una guía telefónica: para un nombre que empieza por T, la abres cerca del final, no por la mitad. Estima la posición del valor buscado a partir de los valores de los dos extremos de la parte que queda. Elige el valor y la distribución, recorre los sondeos paso a paso y descubre cuándo la estimación supera a la búsqueda binaria y cuándo no. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. La línea discontinua marca el valor que buscas, y la parte sombreada indica dónde puede estar todavía. La búsqueda por interpolación necesita una lista ordenada, así que una lista sin ordenar se ordena primero. Elige el valor, cómo se distribuyen los valores, cuántas barras hay, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige el valor que buscar, cómo se distribuyen los valores y cuántas barras hay. O escribe tus propios números: la búsqueda por interpolación los ordena primero.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
  3. Cambia «Distribución» entre «Uniforme», «Huecos aleatorios» y «Sesgada», y compara «Sondeos» con «La búsqueda binaria necesitaría».

Cómo funciona la búsqueda por interpolación

Mira el primer y el último valor de la parte de la lista ordenada que aún puede contener el valor buscado. Si el valor buscado está, por ejemplo, al 40% del camino entre el primer valor y el último, sondea la posición situada al 40% de la lista. Si el valor de esa posición es el buscado, has terminado. Si es menor, solo quedan las posiciones posteriores; si es mayor, solo las anteriores. Vuelve a estimar en lo que queda. Si el valor buscado es menor que el primer valor o mayor que el último, no está.

Cuándo funciona la estimación

Si los valores están distribuidos uniformemente, como 10, 20, 30 y así sucesivamente, la primera estimación cae en el valor buscado o muy cerca, y la búsqueda necesita de media unos log₂(log₂ n) sondeos: unos 5 para mil millones de valores, frente a 30 de la búsqueda binaria. Si los valores se amontonan, como 1, 2, 3, 4, 1000, las estimaciones caen una y otra vez en el lugar equivocado y cada sondeo puede descartar un solo valor, así que el peor caso son n sondeos. La búsqueda binaria nunca necesita más de unos log₂ n.

Preguntas frecuentes

¿Cómo funciona la búsqueda por interpolación?

En una lista ordenada, estima dónde debería estar el valor buscado a partir del primer y el último valor de la parte que queda, sondea esa posición y se queda solo con la parte del lado correcto. Es como la búsqueda binaria, pero con una estimación más lista que el centro.

¿Es la búsqueda por interpolación más rápida que la búsqueda binaria?

Con valores distribuidos uniformemente, sí: de media unos log₂(log₂ n) sondeos en lugar de unos log₂ n. Con valores distribuidos de forma desigual puede ser mucho más lenta, hasta n sondeos, mientras que la búsqueda binaria nunca necesita más de unos log₂ n.

¿Por qué puede ser lenta?

Porque la estimación supone que los valores crecen de forma uniforme. Si la mayoría de los valores son pequeños y unos pocos enormes, la estimación para un valor buscado pequeño cae una y otra vez cerca del principio y solo descarta uno o dos valores cada vez.

¿Dónde se usa la búsqueda por interpolación?

Donde las claves están distribuidas de forma casi uniforme y los sondeos son caros, como al buscar registros en disco por ID numérico o hash. Muchos sistemas la combinan con la búsqueda binaria para mantener un buen peor caso.

¿Se envían mis números a algún sitio?

No. La búsqueda se ejecuta en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

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

Ir al editor