Busqueda Secuencial

INTRODUCCION

La búsqueda de un archivo en un directorio…
La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivosexternos). Todos los algoritmos de búsqueda tienen dos finalidades:
-Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.
-Si el elemento está en el conjunto, hallar la posición en la que se encuentra.

















BUSQUEDA SECUENCIAL

La búsqueda secuencial, también conocida como búsqueda lineal, busca un elemento de unalista o vector utilizando un valor destino llamado clave. En una búsqueda secuencial, los elementos de una lista o vector se examinan en secuencia, uno después de otro. Este método de búsqueda funcionará bien con vectores pequeños o no ordenados. La eficiencia de la búsqueda secuencial es pobre, tiene complejidad lineal, O(n). Sin embargo es necesaria, por ejemplo, si se desea encontrar lapersona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad. Los directorios de teléfonos están organizados alfabéticamente por el nombre del abonado en lugar de por números de teléfono, de modo que deben explorarse todos los números, uno después de otro, esperando encontrar el número 958-220000.
El algoritmo comienza en el primer elemento de la lista o vector(0) o bien en una posición predeterminada (inicio) y recorre los restantes elementos de las listas, comprobando cada elemento con la clave. La exploración continúa hasta que se encuentra la clave o se termina la lista.
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 llave particular, se requiere buscar en toda la lista. Sin embargo existen algunos métodos para mejorar la eficiencia de la búsqueda secuencial:

Mejoras en la eficiencia de la búsqueda secuencial

* Muestreo de acceso
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a lasprobabilidades 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 exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.
* Transposición
Este es otro esquema dereorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros.Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.
* Ordenamiento
Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenarlos registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

Complejidad de la búsqueda lineal...