Búsqueda de interpolación

Búsqueda por interpolación es un algoritmo para buscar una clave en una matriz que ha sido ordenada por valores numéricos asignados a las claves (valores clave). Fue descrita por primera vez por W. W. Peterson en 1957. La búsqueda por interpolación se asemeja al método por el cual las personas buscan un nombre en una guía telefónica (el valor clave por el cual se ordenan las entradas del libro): en cada paso, el algoritmo calcula dónde en el espacio de búsqueda restante podría ser el elemento buscado, en función de los valores clave en los límites del espacio de búsqueda y el valor de la clave buscada, generalmente a través de una interpolación lineal. El valor clave encontrado realmente en esta posición estimada se compara luego con el valor clave que se busca. Si no es igual, dependiendo de la comparación, el espacio de búsqueda restante se reduce a la parte anterior o posterior a la posición estimada. Este método solo funcionará si los cálculos sobre el tamaño de las diferencias entre los valores clave son sensatos.

En comparación, la búsqueda binaria siempre elige la mitad del espacio de búsqueda restante, descartando una mitad o la otra, dependiendo de la comparación entre la clave encontrada en la posición estimada y la clave buscada; no requiere valores numéricos para la llaves, solo un pedido total en ellas. El espacio de búsqueda restante se reduce a la parte anterior o posterior a la posición estimada. La búsqueda lineal usa la igualdad solo porque compara los elementos uno por uno desde el principio, ignorando cualquier clasificación.

En promedio, la búsqueda por interpolación realiza comparaciones de log(log(n)) (si los elementos están distribuidos uniformemente), donde n es el número de elementos a ser buscado En el peor de los casos (por ejemplo, cuando los valores numéricos de las teclas aumentan exponencialmente), puede hacer comparaciones de hasta O(n).

En la búsqueda secuencial por interpolación, la interpolación se usa para encontrar un elemento cercano al que se está buscando, luego la búsqueda lineal se usa para encontrar el elemento exacto.

Rendimiento

Usando la notación O grande, 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 demostrar que el rendimiento es O(log log n). Sin embargo, la búsqueda de interpolación dinámica es posible en tiempo o(log log n) usando una nueva estructura de datos.

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

Las estructuras de índice como los árboles B también reducen la cantidad de accesos al disco y se usan más a menudo para indexar datos en el disco, en parte porque pueden indexar muchos tipos de datos y se pueden actualizar 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.

Adaptación a diferentes conjuntos de datos

Cuando las claves de clasificación para un conjunto de datos son números distribuidos uniformemente, la interpolación lineal es fácil de implementar y encontrará un índice muy cercano al valor buscado.

Por otro lado, para una guía telefónica ordenada por nombre, no se aplica el método sencillo de búsqueda por interpolación. Sin embargo, aún se pueden aplicar los mismos principios de alto nivel: uno puede estimar la posición de un nombre en la guía telefónica usando las frecuencias relativas de las letras en los nombres y usar eso como una ubicación de prueba.

Algunas implementaciones de búsqueda de interpolación pueden no funcionar como se esperaba cuando existe una serie de valores clave iguales. La implementación más simple de la búsqueda por interpolación no seleccionará necesariamente el primer (o último) elemento de dicha ejecución.

Búsqueda basada en libros

La conversión de nombres en una guía telefónica a algún tipo de número claramente no proporcionará números que tengan una distribución uniforme (excepto mediante un gran esfuerzo, como ordenar los nombres y llamarlos nombre #1, nombre #2, etc.) y Además, es bien sabido que algunos nombres son mucho más comunes que otros (Smith, Jones,) Lo mismo ocurre con los diccionarios, donde hay muchas más palabras que comienzan con unas letras que con otras. Algunos editores se esfuerzan por preparar anotaciones marginales o incluso cortar los lados de las páginas para mostrar marcadores para cada letra, de modo que de un vistazo se pueda realizar una interpolación segmentada.

Implementación de muestra

El siguiente ejemplo de código C++ es una implementación simple. En cada etapa, calcula una posición de sonda y luego, al igual que con la búsqueda binaria, mueve el límite superior o inferior para definir un intervalo más pequeño que contiene el valor buscado. A diferencia de la búsqueda binaria que garantiza una reducción a la mitad del tamaño del intervalo con cada etapa, una interpolación errónea puede reducir la eficiencia del caso/i de O(n).

/*T debe implementar los operadores -, !=, ==,tal que не=, не=, !=, == y י define un orden total en T ytales que(tm - tl) * k / (th - tl)es una int entre 0 y k (inclusive) para cualquier tl, tm, th en T con tl.arr debe ser arreglado según este pedido.returns Un índice i tal que arr[i] == llave o -1 si no hay i que satisfaga esto.*/plantilla .nombre T■int interpolation_search()T arr[], int tamaño, T clave){} int bajo = 0; int alto = tamaño - 1; int mitad; mientras ()arr[alto] ! arr[bajo]) " ()clave >= arr[bajo]) " ()clave . arr[alto]) {} mitad = bajo + ()clave - arr[bajo]) * ()alto - bajo) / ()arr[alto] - arr[bajo]) si ()arr[mitad] . clave) bajo = mitad + 1; más si ()clave . arr[mitad]) alto = mitad - 1; más retorno mitad; } si ()clave == arr[bajo]) retorno bajo; más retorno -1;}

Observe que después de probar la lista en el índice medio, por razones de administración de control de bucle, este código establece que alto o bajo sea no mid sino un índice adyacente, cuya ubicación luego se sondea durante la siguiente iteración. Dado que el valor de una entrada adyacente no será muy diferente, el cálculo de la interpolación no mejora mucho con este ajuste de un solo paso, a costa de una referencia adicional a la memoria distante, como el disco.

Cada iteración del código anterior requiere entre cinco y seis comparaciones (el extra se debe a las repeticiones necesarias para distinguir los tres estados de < > y = a través de comparaciones binarias en ausencia de una comparación triple) más algo de aritmética desordenada, mientras que el algoritmo de búsqueda binaria se puede escribir con una comparación por iteración y usa solo aritmética de enteros trivial. Por lo tanto, buscaría una matriz de un millón de elementos con no más de veinte comparaciones (lo que implica accesos a la memoria lenta donde se almacenan los elementos de la matriz); para superar eso, la búsqueda de interpolación, como se escribió anteriormente, no se permitiría más de tres iteraciones.