Metodo De Busqueda

INSTITUTO TECNOLOGICO SUPERIOR DE ALVARADO
CAMPUS LERDO DE TEJADA

INGENIERIA: SISTEMAS COMPUTACIONALES
MATERIA
ESTRUCTURA DE DATOS
TEMA
Métodos de busqueda
SEMESTRE- GRUPO
3A
PRESENTA
RAUL CARVALLO ORTIZ
DOCENTE
ALFONSO ROJASESCOBEDO

H. Y G. ALVARADO, VER. AGOSTO–DICIEMBRE 2012

MÉTODOS DE BÚSQUEDA UNIDAD 6

INDICE

6.1 Búsqueda secuencial

6.2 Búsqueda binaria

6.3 Búsqueda por funciones de HASH

INTRODUCCION

Los algoritmos de búsqueda que se exponen a continuación se aplican a árboles. Como se verá, muchos problemas de optimización pueden modelarse de manera de generar un árbol cuyos nodosconstituyen posibles soluciones o pasos intermedios a la solución del problema; cada uno de estos algoritmos define un orden en el cual se generarán los nodos del árbol, y una forma en la cual se encontrará la solución buscada.

6.1. MÉTODO DE BÚSQUEDA SECUENCIAL

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ú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 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 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 parahacer 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 LA BÚ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 se mueve 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 enque, 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 detransposició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. 

4)Ordenamiento

Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor dela 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.

EJEMPLO DE BÚSQUEDA SECUENCIAL
El siguiente programa cumple con los...