martes, 11 de noviembre de 2008

tecnicas de busqueda por interpolación

Pertenece a:
  • Christian Ruiz
  • Melissa Garcia
Técnica de Búsqueda por Interpolación.

Descripción de la técnica:

Este método se puede aplicar solamente a tablas o archivos ordenados. Como su nombre lo indica se trata de llegar al elemento buscado por medio de la interpolación lineal.
El procedimiento es recursivo; como en el caso de la búsqueda binaria, en cada paso se van modificando los límites, disminuyendo el intervalo, hasta llegar al elemento buscado.
Si se determina que la clave buscada XX se encuentra dentro del intervalo INTABLA de la tabla, y que la variación en ese intervalo de la clave es INCLAVE, la siguiente posición a probar es:

PX = PI + ENTERO ((XX-XI) * (INTABLA / INCLAVE))

El algoritmo es similar al de búsqueda binaria, la diferencia está en que en vez de dividir el área en mitades, se delimita por medio de los valores resultantes de la interpolación.

En búsqueda binaria el espacio se corta siempre adentro a medias, las garantías de lo que desea el funcionamiento logarítmico.
Sin embargo, durante la búsqueda encontramos un valor que esté muy cerca del número z de la búsqueda, parece más razonable continuar la búsqueda en esa Área en vez de ocultar e ir a la media punta siguiente.
En detalle, si z es muy pequeño, debemos comenzar la búsqueda en alguna parte en el principio de la secuencia en vez de la punta intermedia Considere la manera que abrimos un libro cuando estamos buscando para cierta página. Diga que la página es 200 y el libro parece de 800 paginas.

La paginación 200 es así alrededor de la marca de un cuarto, y nosotros utilizamos este conocimiento como indicación de donde abrir el libro.
No golpearemos probablemente la paginación 200 en el primer intento; suponga que conseguimos la paginación 250 en lugar de otro.
Ahora cortamos la búsqueda a un rango de 250 paginas, y la paginación deseada está en alrededor la marca de 80 por ciento entre la paginación 1 y 250.
Ahora intentamos ir detrás de un quinto de la manera corta. Podemos continuar este proceso hasta que conseguimos bastante cercanos a la paginación 200, de que podemos mover de un tirón una pagina al mismo tiempo.
Ésta es exactamente la idea detrás de la búsqueda de la interpolación. En vez de cortar el espacio de la búsqueda por una mitad fija, la cortamos por una cantidad que se parezca la más probable tener éxito.
El funcionamiento de la búsqueda de la interpolación depende no solamente de la talla de la secuencia, pero también de la entrada de información misma. Hay entradas de información para los chequeos de la búsqueda de interpolación del deseado en cada número en la secuencia. Sin embargo, la búsqueda de la interpolación es muy eficiente para las entradas de información que consisten en elementos relativamente uniformemente distribuidos (las paginaciones de un libro, por supuesto, se distribuyen uniformemente).
Puede ser mostrado que el número medio de comparaciones se realizó por la búsqueda de interpolación, donde el promedio asume el control todas las secuencias posibles, es 0 (logn del registro). Aunque éste se parece ser un orden de la mejora magnitud concluída de el funcionamiento de la búsqueda binaria ( debido al logaritmo adicional).
Ventajas de la técnica.

La búsqueda de interpolación, es una búsqueda mucho mejor que la binaria en la práctica porque, a menos que no sea muy grande, el valor de log2n es bastante pequeño que el logaritmo de él no es mucho más pequeño.
Incluso a pesar de qe el calclo es de algun modo mas complejo, una busqueda con interpolacion puede proporcionar una mejoria importante a nuestra busqueda binaria en grandes conjuntos de datos con claves distribuidas de modo uniforme.

Desventajas de la técnica.
  • La búsqueda de la interpolación requiere una aritmética más elaborada, a parte que los calculos que se necesitan para esta busqueda son muy lentos.
  • Para lograr esta busqueda se requieren llaves, multiplicaciones y divisiones complejas, es decir, calculos de nivel alto.

Principales Aplicaciones.


En aplicaciones matematicas donde se busquen aproximaciones de alguna ecuacion, se utiliza este metodo pero sin su recursividad solo hace su primera para conseguir las aprox.
Tambien tiene las mismas aplicaciones que la busqueda binaria ya que son casi iguales.

Codificación.


#define MEDIO (x) ( ((x) + 1)/2 )
#define NO_ ENCONTRAD

int bus_bin (int datos [], int tamaño, int clave)

{
int delta,mitad;
delta =tamaño / 2;
while (clave := datos[mitad] ) {
if (delta ==0)
return (NO_ENCONTRADO);
else if(clave>datos[mitad]);
mitad + = medio (delta);
else
mitad -= MEDIO (delta);
delta=delta/2;
}
return (mitad);
}