METODOS DE BUSQUEDA

BUSQUEDA

La BUSQUEDA , es una operación que permite recuperar datos previamente almacenados. El resultado puede ser exitoso si se encuentra el elemento solicitado, o fracaso, en otro caso.

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.