Sistemas

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 registrosdel 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 losregistros 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 cuyoapellido 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 deproporcionalidad. 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 losvalores de las siguientes claves :
o Clave mas baja, que llamamos Kl ( l de low )
o Clave de búsqueda, que llamammos K
o clave de interpolación, que llamamos Ki
o 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 :
o Kl es la clave mas baja ( low )
o Ku es la clavemas alta ( up )
o K es la clave de búsqueda
o 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...