Búsqueda por interpolación

La búsqueda por interpolación es un algoritmo para buscar una clave en una matriz ordenada por valores numéricos asignados a las claves ( valores de clave ). Fue descrita por primera vez por W. W. Peterson en 1957. ^{[ 1 ]} La búsqueda por interpolación se asemeja al método que se utiliza para buscar un nombre en una guía telefónica (el valor de clave que ordena las entradas del directorio): en cada paso, el algoritmo calcula la posición del elemento buscado en el espacio de búsqueda restante , basándose en los valores de clave en los límites del espacio de búsqueda y el valor de la clave buscada, generalmente mediante una interpolación lineal . El valor de clave encontrado en esta posición estimada se compara con el valor de clave buscado. Si no coinciden, según 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 funciona si los cálculos sobre la magnitud de las diferencias entre los valores de clave son razonables.

En comparación, la búsqueda binaria siempre elige el punto medio del espacio de búsqueda restante, descartando una mitad u otra según la comparación entre la clave encontrada en la posición estimada y la clave buscada; no requiere valores numéricos para las claves, solo un orden total de las mismas. El espacio de búsqueda restante se reduce a la parte anterior o posterior a la posición estimada. La búsqueda lineal utiliza únicamente la igualdad, ya que compara los elementos uno por uno desde el principio, sin tener en cuenta ningún ordenamiento.

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

En la búsqueda secuencial por interpolación, se utiliza la interpolación para encontrar un elemento cercano al que se busca, y luego se utiliza la búsqueda lineal para encontrar el elemento exacto.

Utilizando la notación de la gran 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 demostrar que el rendimiento es O (log log n ). ^{[ 3 ] [ 4 ] [ 5 ]}

La búsqueda de interpolación dinámica extiende el límite o (log log n ) a otras distribuciones y también admite inserción y eliminación O (log n ). ^{[ 6 ] [ 7 ]}

El rendimiento práctico de la búsqueda por interpolación depende de si la reducción en el número de sondeos compensa los cálculos más complejos necesarios para cada uno. Puede ser útil para localizar un registro en un archivo grande ordenado en disco, donde cada sondeo implica una búsqueda en 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 el número de accesos al disco y se utilizan con mayor frecuencia para indexar datos en disco, en parte porque pueden indexar muchos tipos de datos y se pueden actualizar en línea . Aun así, la búsqueda por interpolación puede ser útil cuando se requiere buscar en conjuntos de datos en disco ordenados pero no indexados.

Cuando las claves de ordenación de 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, el método directo de búsqueda por interpolación no es aplicable. Sin embargo, se pueden aplicar los mismos principios generales: se puede estimar la posición de un nombre en la guía telefónica utilizando la frecuencia relativa de las letras en los nombres y usar ese valor como punto de referencia.

Es posible que algunas implementaciones de búsqueda por interpolación no funcionen como se espera cuando existe una secuencia de valores de clave iguales. La implementación más simple de búsqueda por interpolación no necesariamente seleccionará el primer (o último) elemento de dicha secuencia.

La conversión de nombres en una guía telefónica a algún tipo de número claramente no dará como resultado números con una distribución uniforme (a menos que se realice un esfuerzo inmenso, como ordenar los nombres y llamarlos nombre n.° 1, nombre n.° 2, etc.). 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 ciertas letras que con otras. Algunos editores se toman la molestia de preparar anotaciones marginales o incluso de hacer cortes en el lateral de las páginas para mostrar marcadores para cada letra, de modo que se pueda realizar una interpolación segmentada de un vistazo.

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

importar <cassert> ;​​importar std ;usando std :: vector ;/*arr[low, high) está ordenado, busque los datos "clave" en este array,Si se encuentra la "clave", devuelva el índice correspondiente (NO necesariamente el índice más alto posible);Si no se encuentra la "clave", simplemente devuelve low - 1.¿Cómo verificar que el algoritmo es correcto?Prueba:(finitud: después de un bucle, el ancho de [bajo, alto] disminuye estrictamente)Puño, alto <--- alto - 1escenario 1. cuando bajo = altoEscenario 2. Cuando bajo < alto, arr[bajo] = arr[alto]escenario 3. cuando low < high, arr[low] < arr[high], key < arr[low] o key > arr[high]escenario 4. cuando bajo < alto, arr[bajo] < arr[alto], arr[bajo] <= clave <= arr[alto]Ahora analicemos el escenario 4:Una vez que se entra en el bucle "while", bajo <= medio <= alto Analicemos después de un bucle (si no devolvemos nada), si ocurrirá "low > high". Después de un bucle: caso a1: la rama "low" se ha ejecutado en este bucle. arr[medio] < tecla <= arr[alto] entonces tenemos medio < alto Entonces, después de este bucle, tenemos bajo <= alto caso a2: la rama "high" se ha ejecutado en este bucle. arr[low] <= key < arr[middle] por lo tanto tenemos bajo < medio Entonces, después de este bucle, tenemos bajo <= alto Entonces, después de un bucle (si no devolvemos nada), tenemos "bajo <= alto". Cuando salimos del bucle "while": caso b1: arr[bajo] >= arr[alto] En el último bucle, si se ejecuta la rama "baja", sabemos arr[bajo - 1] < k <= arr[alto] arr[bajo] >= arr[alto] bajo <= alto así que tenemos arr[bajo - 1] < k <= arr[bajo] = arr[alto] En el último bucle, si se ejecuta la rama "alta", sabemos arr[low] <= key < arr[high + 1] arr[bajo] >= arr[alto] bajo <= alto así que tenemos arr[low] = arr[high] <= key < arr[high + 1] caso b2: (arr[low] < arr[high]) && (arr[low] > key): En el último bucle, "bajo" debe haber sido cambiado. así que tenemos arr[bajo - 1] < tecla así que tenemos arr[bajo - 1] < clave < arr[bajo] caso b3: (arr[bajo] < arr[alto]) && (clave > arr[alto]) En el último bucle, "alto" debe haber sido cambiado. así que tenemos clave < arr[alto + 1] así que tenemos arr[bajo] < arr[alto] < clave < arr[alto + 1]*/// versión 1plantilla < typename T >static Rank interpolationSearch ( vector < T >& arr , const T & key , Rank low , Rank high ) {alto -= 1 ;entero medio ;int initialLow = bajo ;mientras (( arr [ low ] < arr [ high ]) && ( arr [ low ] <= key ) && ( key <= arr [ high ])) {medio = bajo + (( clave - arreglo [ bajo ]) * ( alto - bajo )) / ( arreglo [ alto ] - arreglo [ bajo ]);afirmar (( bajo <= medio ) && ( medio <= alto ));si ( arr [ medio ] < clave ) {bajo = medio + 1 ;} else if ( key < arr [ middle ]) {alto = medio - 1 ;} demás {regresar al medio ;}}si ( clave == arr [ bajo ]) {retorno bajo ;} demás {devolver initialLow - 1 ;}}/*buscar "clave" en el array ordenado arr[low, high),Devuelve: el índice más alto i tal que arr[i] <= clave¿Cómo verificar que el algoritmo es correcto?Prueba:finitud: después de un bucle, el ancho de [bajo, alto] disminuye estrictamentePuño, alto <---- alto - 1escenario 1. cuando bajo = altoEscenario 2. Cuando low < high, key < arr[low] o arr[high] <= keyescenario 3. cuando bajo < alto, arr[bajo] <= clave < arr[alto]Ahora analicemos el escenario 3:Una vez que se entra en el bucle "while", bajo <= medio < altoCuando salimos del bucle "while": caso a1: clave < arr[bajo] por lo que "bajo" se cambia en el último bucle, lo sabemos arr[low - 1] <= key < arr[low] caso a2: arr[high] <= clave por lo que "alto" se cambia en el último bucle, lo sabemos clave < arr[high], imposibleConclusión: deberíamos devolver "bajo - 1".*/// versión 2plantilla < typename T >static Rank interpolationSearch ( vector < T >& arr , const T & key , Rank low , Rank high ) {alto -= 1 ;afirmar ( bajo <= alto );Rango medio ;si ( clave < arr [ bajo ]) {devolver bajo - 1 ;}si ( arr [ high ] <= key ) {devolver alto ;}// ahora bajo < alto , arr[bajo] <= clave < arr[alto]mientras (( arr [ low ] <= key ) && ( key < arr [ high ])) {medio = bajo + (( alto - bajo ) * ( clave - arreglo [ bajo ])) / ( arreglo [ alto ] - arreglo [ bajo ]);afirmar (( bajo <= medio ) && ( medio < alto ));si ( clave < arr [ medio ]) {alto = medio ;} demás {bajo = medio + 1 ;}}devolver bajo - 1 ;}

Nótese que, tras sondear la lista en el índice mid , por motivos de control del bucle, este código asigna a high o low un índice adyacente en lugar de mid , cuya ubicación se sondea en la siguiente iteración. Dado que el valor de una entrada adyacente no será muy diferente, este ajuste de un solo paso no mejora significativamente el cálculo de interpolación, a costa de una referencia adicional a una memoria distante, como el disco.

Cada iteración del código anterior requiere entre cinco y seis comparaciones (las adicionales se deben a las repeticiones necesarias para distinguir los tres estados de < > y = mediante comparaciones binarias en ausencia de una comparación triple ), además de algunas operaciones aritméticas complejas, mientras que el algoritmo de búsqueda binaria se puede escribir con una comparación por iteración y utiliza únicamente aritmética entera trivial . De este modo, buscaría en un array de un millón de elementos con no más de veinte comparaciones (que implican accesos a la memoria lenta donde se almacenan los elementos del array); para superarlo, la búsqueda por interpolación, tal como se describe anteriormente, no podría requerir más de tres iteraciones.

• Búsqueda lineal
• Búsqueda binaria
• Búsqueda binaria interpolada , ^{[ 8 ]} un híbrido de búsqueda interpolada y búsqueda binaria
• Búsqueda exponencial
• Búsqueda ternaria
• Tabla hash
• El método de Newton
• Flashsort , que utiliza la distribución de valores para ordenar en lugar de buscar.

• Búsqueda por interpolación
• Instituto Nacional de Estándares y Tecnología
• Búsqueda por interpolación: una búsqueda Log LogN