Algoritmos De B Squeda

Introducción.


     Una tabla o un archivo es un grupo de elementos, cada uno de los cuales se llama registro. Hay una llave asociada a cada registro, que se usa para diferenciar unos de otros. La asociacion entre un registro y su llave puede ser simple o compleja. En la  forma mas simple, la llave esta contenida dentro del registro en un tramo a una  distancia especifica del principio delmismo. Una llave de ese tipo es la llave interna o incluida.
 
En este trabajo, se veran las tecnicas de busqueda secuencial ordenada/desordenada, secuecial idexada, binaria e interpolacion. En cada una se mencionan su descripcion, sus venajas/desventajas, y algunas aplicaciones, por supuesto tambien se eran sus respectivos algritmos, ¿pero que es un algoritmo de busqueda?.
    
     Un algoritmode busqueda es un algoritmo que acepta un argumento a y trata de encontrar un registro cuya llave sea a. El algoritmo puede dar como resultado el registro entero o, lo que es mas comun, un apuntador a dicho registro.
 
     Si la busqueda es  infructuosa, con mucha frecuencia, es deseable agregar un nuevo registro con dicho argumento como llave. Un algoritmo que haga  esto se le llama tabla busqueda o diccionario.
 
     La  busqueda en la cual toda la tabla esta de manera frecuente en la memoria principal se le llama busqueda interna, mientras que  la busqueda en la que la mayor parte de la table esta en la memoria auxiliar se llama busqueda externa.






















PARTE I:

Técnica Secuencial Ordenada/Desordenada.

1.1 Descripción de la técnica.

La búsqueda es el proceso delocalizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.
 
Normalmente un archivo secuencial se almacena en bloques, en un orden secuencial simple de los registros. La organización física del archivo en unacinta o disco se corresponde exactamente con la ubicación lógica del archivo. En este caso, el procedimiento para ubicar los nuevos registros en un archivo de pila separado, llamado archivo de registro (log file) o archivo de transacciones. Periódicamente, se realiza una actualización por lotes que mezcla el archivo de registro con el archivo maestro para producir un nuevo archivo en secuenciacorrecta de claves.

Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista.
 

  La situación óptima es que el registro buscado seael primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones.
 
Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llaveparticular, se requiere buscar en toda la lista.

1.2 Ventajas de la técnica. 

Es el algoritmo más simple de búsqueda y no requiere ningún proceso previo de la tabla, ni ningún conocimiento sobre la distribución de las llaves. La búsqueda secuencial es el área del problema donde previamente existían mejores algoritmos.

Es el mejor metodo de busqueda para registros desordenados y revisa nodopor nodo sin brincar ninguno ( es muy seguro)

Muestreo de acceso:
 
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas.
 
Movimiento hacia el frente:
 
Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea...