Metodos De Busqueda

Técnica Secuencial Ordenada/Desordenada.
1.1 Descripción de la técnica.
La búsqueda es el proceso de localizar 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 sealmacena en bloques, en un orden secuencial simple de los registros. La organización física del archivo en una cinta 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 lotesque mezcla el archivo de registro con el archivo maestro para producir un nuevo archivo en secuencia correcta 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 llaveindicada (k), o hasta al final de la lista.
 
[pic]



Técnica de Búsqueda Secuencial Indexada.
2.1 Descripción de la técnica.
Un método popular para superar las desventajas de los archivos secuenciales es el del archivo secuencias indexado; pero implica un aumento en la cantidad de espacio requerida.
Funciona de la siguiente manera:
Se reserva una taba auxiliar llamada indice ademasdel archivo ordenado mismo. Cada elemento en el indice consta de una llave kindex y un apuntador al registro en el archivo que corresponde a kindex. Los elementos en el indice al igual que los elementos en el archivo, deben estar ordenados en la llave. Si el indice es de un octavo del tamaño del archivo, se representa en el indice cada octavo registra el archivo.
[pic]
Si el indice comienza acrecer tanto que se vuelve ineficaz se puede usar un indice secundario que funciona casi de la misma forma que el indice principal, solo que apunta a este, no a la tabla principal la busqueda empieza con una exploracion por el indice secundario; esto nos lleva a un subarreglo en el indice principal; despues el procesamiento continua normalmente. Un ejemplo de lo anterior es la siguiente figura.
[pic]Técnica de Búsqueda Binaria.
3.1 Descripción de la técnica.
Si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina búsqueda binaria.
La búsqueda binaria utiliza un método de `divide y vencerás'para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado,entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este porceso, utilizando el elemento central de esa sublista.
Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:
• La lista debeestar ordenada en un orden específico de acuerdo al valor de la llave.
• Debe conocerse el número de registros.

Técnica de Búsqueda por Interpolación.
4.1 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; comoen 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...