Metodos de busquedas

Metodos de Busquedas
Busqueda Secuencial
Definicion:
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando selocaliza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.
Búsqueda secuencial, también se le conoce como búsquedalineal. 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 hastaencontrar la llave indicada (k), o hasta al final de la lista.

La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los nregistros 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 emplearsepara 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.
Mejoras en la eficiencia de labúsqueda secuencial
1)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.2)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 semueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.
3)Transposición
Este es otro esquema de reorganizació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...