¿Qué es la búsqueda de interpolación en estructuras de datos?

La búsqueda de interpolación es una versión mejorada del algoritmo de búsqueda binaria.

Hay casos en que la ubicación de los datos objetivo puede conocerse de antemano. Por ejemplo, en el caso del directorio telefónico, si queremos buscar el número de teléfono de Morphius. Aquí, la búsqueda lineal e incluso la búsqueda binaria parecerán lentas ya que podemos saltar directamente al espacio de memoria donde se almacenan los nombres que comienzan desde ‘M’.

Posicionamiento en Búsqueda Binaria

En la búsqueda binaria, si no se encuentran los datos deseados, el resto de la lista se divide en dos partes, inferior y superior. Luego, la búsqueda se realiza en cualquiera de ellos.

Incluso cuando los datos están ordenados, la búsqueda binaria no aprovecha eso para sondear la posición de los datos deseados.

Sondeo de posición en la búsqueda de interpolación

La búsqueda por interpolación busca un elemento en particular calculando la posición de la sonda. Inicialmente, la posición de la sonda es la posición del elemento más intermedio de la colección.

Si se produce una coincidencia, se devuelve el índice del elemento.

Para dividir la lista en dos partes, utilizamos el siguiente método

mid = low + ((A [high] – A [low]) * (high – low)) / (x – A [low])

donde –

A = lista o matriz

Bajo = índice más bajo de la lista

Alto = índice más alto de la lista

A [n] = Valor almacenado en el índice n en la lista

x = x es la clave que se busca

Si el ítem central es mayor que el ítem, la posición de la sonda se calcula nuevamente en el subconjunto a la derecha del ítem central; de lo contrario, se busca en el subarreglo a la izquierda del ítem central. Este proceso también continúa en la submatriz hasta que el tamaño de la submatriz se reduce a cero.

La complejidad del tiempo de ejecución del algoritmo de búsqueda de interpolación es Ο (log (log n)) en comparación con Ο (log n) del Algoritmo de búsqueda binaria en situaciones favorables.

Fuente: Tutorialspoint

Para obtener un video tutorial detallado sobre la búsqueda de interpolación, consulte: Búsqueda de interpolación en Codewhoop

• La búsqueda de interpolación es una mejora sobre la búsqueda binaria.
• La búsqueda binaria siempre verifica el valor en el índice medio. Pero, la búsqueda de interpolación puede verificar en diferentes ubicaciones según el valor del elemento que se busca.
• Para que la búsqueda de interpolación funcione de manera eficiente, los elementos / datos de la matriz deben clasificarse y distribuirse uniformemente.
• En casos favorables tiene una complejidad temporal de O (log log n) pero en el peor de los casos es O (n)

Pasos:

• A – Matriz de elementos, e – elemento a buscar, pos – posición actual
• Hacer inicio = 0 y fin = n-1
• calcule la posición (pos) para comenzar a buscar usando la fórmula:

• Si A [pos] == e , elemento encontrado en pos. Índice.
• De lo contrario, si e> A [pos] hacemos start = pos + 1
• De lo contrario, si e hacemos end = pos -1
• Repetir Mientras: inicio <= fin && e> = A [inicio] && e =

Lamento las solicitudes de respuesta accidental enviadas a algunos usuarios, ya que pensé que el signo ‘+’ revelaría más opciones. Al principio me sorprendió ver solo una marca de verificación, pero mucho después entendí lo que era.