Búsqueda de interpolación vs búsqueda binaria

¿Cuándo debería usar la búsqueda de interpolación en lugar de la búsqueda binaria?

Por ejemplo, tengo un conjunto de datos ordenado, ¿en qué situaciones usaría la búsqueda binaria para encontrar un elemento en este conjunto de datos o en qué situación debería usar la búsqueda de interpolación?

¿Qué propiedades del conjunto de datos serían el factor determinante?

Obviamente, para realizar una búsqueda de interpolación, necesita algún tipo de clave para la que se conoce más que el orden: debe ser capaz de hacer cálculos en las teclas para estimar una distancia probable, no solo comparar teclas para determinar cuál es mayor o mayor. menor.

En cuanto a las propiedades del conjunto de datos, se trata principalmente de una propiedad: la probabilidad de que las claves se distribuyan de manera razonablemente uniforme (o al menos predecible) en todo el rango de posibilidades. Sin eso, una búsqueda de interpolación puede ser más lenta que una búsqueda binaria.

Por ejemplo, considere un conjunto de datos con cadenas de letras minúsculas como claves. Supongamos que tiene una clave que comienza con "x". Una búsqueda de interpolación indicará claramente que debe comenzar a buscar muy cerca del final del conjunto. Sin embargo, si la mayoría de sus claves realmente comienzan con 'z', y casi ninguna con algo de 'a' aunque 'y', la que está buscando puede estar muy cerca del comienzo del conjunto. Puede / puede tomar un número considerable de iteraciones antes de que la búsqueda se acerque al comienzo donde reside la cadena que comienza con 'w'. Cada iteración eliminaría solo ~ 10% del conjunto de datos de la consideración, por lo que tomaría varias iteraciones antes de acercarse al principio donde las teclas que comienzan con 'w'

Por el contrario, una búsqueda binaria comenzaría en el medio, llegaría a la marca de un cuarto en la segunda iteración, a la octava marca en la tercera, y así sucesivamente. Su rendimiento casi no se vería afectado por el sesgo en las teclas. Cada iteración eliminaría la mitad del conjunto de datos de la consideración, como si las claves estuvieran distribuidas de manera uniforme.

Sin embargo, me apresuro a agregar que realmente se necesita una distribución bastante sesgada para que una búsqueda de interpolación sea notablemente peor que una búsqueda binaria. Por ejemplo, puede funcionar bastante bien incluso en presencia de una buena cantidad de agrupación localizada.

También debo mencionar que una búsqueda de interpolación no necesariamente necesita usar interpolación lineal. Por ejemplo, si se sabe que sus claves siguen una distribución no lineal (por ejemplo, una curva de campana), se hace bastante fácil tener eso en cuenta en la función de interpolación para obtener resultados poco diferentes de tener una distribución uniforme.

Probablemente piense que la pregunta es con qué facilidad puede encontrar una función de interpolación que realmente funcione mejor que la búsqueda binaria.

De Wikipedia en Búsqueda de interpolación:

Usando notación big-O, el rendimiento del algoritmo de interpolación en un conjunto de datos de tamaño N es O (N); sin embargo, bajo el supuesto de una distribución uniforme de los datos en la escala lineal utilizada para la interpolación, se puede mostrar que el rendimiento es O (log log N).

El rendimiento práctico de la búsqueda de interpolación depende de si el número reducido de sondas se ve superado por los cálculos más complicados necesarios para cada sonda. Puede ser útil para localizar un registro en un archivo ordenado grande en el disco, donde cada sonda implica una búsqueda de disco y es mucho más lenta que la aritmética de interpolación.

Las estructuras de índice como los árboles B también reducen el número de accesos a disco, y se usan con mayor frecuencia para indexar datos en disco en parte porque pueden indexar muchos tipos de datos y pueden actualizarse en línea. Aún así, la búsqueda de interpolación puede ser útil cuando uno se ve obligado a buscar ciertos conjuntos de datos en disco ordenados pero no indexados.

La búsqueda binaria y la búsqueda de interpolación se consideran métodos de búsqueda lineal.

Ambos esperan que la lista que se busca se ordene en la columna a la que se hace referencia como clave . Esto es muy importante.

La búsqueda binaria funciona para cadenas o números siempre que estén almacenados en orden ordenado. La idea principal detrás de la búsqueda binaria es que se basa en examinar el elemento del medio. La búsqueda de interpolación es una variante. En lugar de usar el elemento medio exacto, adivina dónde está el siguiente elemento para comparar con el valor pasado. Consulte la referencia proporcionada por la respuesta de JB King o la siguiente en esta respuesta para obtener detalles sobre cómo el algoritmo de búsqueda de interpolación calcula el siguiente valor clave.

"La búsqueda de interpolación funciona solo en elementos numéricos ordenados en orden de matrices ordenadas con distribución uniforme (es decir, el intervalo entre cualquiera de los elementos sucesivos es más o menos constante" (cita de la referencia a continuación P 737, también se incluye una comparación de rendimiento entre diferentes métodos de búsqueda lineal) )

Google Books: estructuras de datos clásicas, 2ª ed.