METODOS DE BUSQUEDA

METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
• Métodos de Búsqueda Interna
• Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
• Secuencial o lineal
• Binaria
• Por transformación de claves
• Arboles de búsqueda
•
METODOS DE BUSQUEDA EXTERNA
• Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
• Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
• CARACTERISTICAS
• La búsqueda se puede realizar en arreglos desordenados.
• El método es totalmente confiable.
• El numero de comparaciones es significativa si el arreglo es muy grande.
• En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+N)/2.
• Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO
(BUSQUEDA SECUENCIAL)
BUSQUEDA 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 proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
• Sirve únicamente para arreglos ordenados.
• Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+log₂(N))/2.
• Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
• Se compara la llave buscada con la llave localizada al centro del arreglo.
• Si la llave analizada corresponde a la buscada fin de búsqueda si no.
• Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
• El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
• Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
• El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
• La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
• Las Funciones HASH (H) mas aplicadas son:
• Función Modulo (Por división).
• Función Cuadrado.
• Función Plegamiento.
• Función Truncamiento.