Estructura de Datos : Búsqueda Interpolada

Definiciones

Las condiciones iniciales son las siguientes :

El archivo donde buscar ya está en memoria, dispuesto en slots contiguos.

Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.

Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo donde buscar.

Todos los registros tienen una clave Ki, donde i es 1 =< i =< n.

Los registros están ordenados respecto de la clave mencionada.

La búsqueda será hecha en los mismos slots donde están los registros.

Los criterios de la búsqueda son los siguientes :

Ni la búsqueda binaria, ni la búsqueda fibonacci, buscan como lo hace el ser humano, por ejemplo, al buscar en la guía telefónica, una persona cuyo apellido empieza con W.
Nosotros tenemos idea de una cierta proporcionalidad, respecto del tamaño del archivo, y vamos directamente a la parte alta de la guía telefónica, siguiendo esa idea de proporcionalidad. En el caso de la búsqueda del apellido que comienza con W vamos a la parte final de la guía.
La idea de la búsqueda interpolada es arriesgar una proporcionalidad basandose en los valores de las siguientes claves :
- Clave mas baja, que llamamos Kl ( l de low )
- Clave de búsqueda, que llamammos K
- clave de interpolación, que llamamos Ki
- Clave mas alta, que llamamos Ku ( u de up )
donde el índice de la clave de interpolación es :
i = ( ( K - Kl ) / ( Ku - Kl ) ) * n = factor de interpolación * n
donde :
- Kl es la clave mas baja ( low )
- Ku es la clave mas alta ( up )
- K es la clave de búsqueda
- n es la cantidad de claves presentes en el archivo o cantidad de registros
Observar que si K = Kl ------> factor de interpolación = ( Kl - Kl ) / ( Ku - Kl ) = 0 / ( Ku - Kl ) = 0; donde para un archivo de 70 registros i = 0 * 70 = 0
Observar que si K = Ku ------> factor de interpolación = ( Ku - Kl ) / ( Ku - Kl ) = 1; donde para un archivo de 70 registros i = 1 * 70 = 70
```
Claves ---->   Kl                                                 Ku
             |<----------------------------------------------------->|
Factor ---->   0                                                   1
Registro -->   1                                                   n
Indice ---->   0                                                   n-1
```

Establecido el ínidce de la clave de interpolación, queda fijado el registro Ri, de clave Ki, y determinados los subarchivos menor y mayor.

               R1                       Ri                        Rn
         ...------------------.......--------..................--------.......
             | Kl |    |    |         | Ki |                    | Ku |              n slots
         ...------------------.......--------..................--------.......


             |<---------------------->|    |<----------------------->|
                  subarchivo menor               subarchivo mayor

             |<-------- Ki - Kl ---------->|

             |<---------------------- Ku - Kl ---------------------->|

Si K = Ki, la clave fué hallada.
Si K < Ki, se repite el procedimiento con el subarchivo menor.
Si K > Ki, se repite el procedimiento con el subarchivo mayor.

Ejercicio : Desarrollar el procedimiento de busqueda interpolada.