MetodosDeBusqueda

Métodos de Búsqueda

f829c536-fcba-4ef8-add6-fda5c5007131 (image/jpg)

Rubrica: : Secuencial | Binaria | De Árbol

Introducción

Una de las funciones que con mayor frecuencia se utiliza en los sistemas de información, es el de las consultas a los datos, se hace necesario utilizar algoritmos, que permitan realizar búsquedas de forma rápida y eficiente.

ea5c8364-db14-48e8-84bc-591df91355ec (image/jpg)

“La operación de búsqueda sobre una estructura de datos es aquella que permite localizar un nodo en particular si es que éste existe."

Tipos de Búsquedas

Comparación de Llaves       *Lineal       *BinariaTransformación de Llaves       *Funciones Hash o de          Dispersión de Mapeo

Búsqueda Secuencial

Este tipo de búsqueda consiste en examinar, a partir del primer elemento y de uno en uno, hasta encontrar el dato buscado o bien llegar al final de la lista que puede estar almacenada en archivo o arreglo.

4c83f2e8-21c3-4b27-b444-d0fe219012dc (image/jpg)

Búsqueda Secuencial

En este tipo de listas los elementos pueden o no estar clasificados, ya que se empieza a comparar de uno en uno los elementos de la lista y no importa su orden para realizar la búsqueda, salvo para el tiempo de ejecución. Si el elemento que se está buscando, se encuentra al inicio de la lista, este tiempo, sería muy corto, pero si se encuentra al final, va a tardar más y si el elemento que se desea buscar, no se encuentra en la lista, se hizo necesario, recorrer toda la lista, para darse cuenta que no está en ella. Y si se le aumenta a esto, que el número de elementos en la lista puede ser del orden de cientos o miles, va a hacer mucho más tardado su ejecución. Esta búsqueda tiene la ventaja de tener una fácil programación de su algoritmo.

aaab5a29-3727-43a4-9291-44598b2bb1c8 (image/jpg)

Búsqueda Binaria

La búsqueda Binaria o por Bisección no representa mucha dificultad para la programación de su algoritmo y además, es muy rápida su ejecución. Este algoritmo requiere que los elementos de la lista, sobre la que va a actuar, estén clasificados, ya sea en forma ascendente o descendente, cada elemento de la lista puede tener varios campos. La lista se considera que empieza a almacenar sus elementos en la posición cero.

Búsqueda Binaria

Va a utilizarse tres apuntadores, uno en la primera posición de la lista que se le denominara LI, para efectos de la explicación, otro en la última conocido como LS y el que apunte en la parte central, el cual se obtiene de la suma de LS mas LI entre dos (LI + LS/ 2) y tomando la parte entera, el cual se le llamará M.A diferencia de la Búsqueda Secuencial, aquí el número de comparaciones no se comporta en forma lineal, ya que procede a realizar los siguientes pasos:

Dividir la lista en dos partes, al determinar el elemento central de dicha lista, con lo que se iniciará el apuntador M. Comparar el valor del elemento buscado con el central. Si resultan ser iguales, las búsquedas termina con éxito, indicando en qué posición se encontró y cuáles son los datos que están en esa posición. En el caso de no ser iguales, se redefinen la posición de alguno de los

apuntadores de los extremos (LI o LS), dependiendo del valor del elemento central, sea mayor o menor que el buscado. Por ejemplo, suponiendo que la lista está clasificada en forma ascendente, se pueden presentar los siguientes casos: Que el elemento buscado sea mayor que el elemento central (apuntado por M), entonces se desechará la primera mitad de la lista ya que por estar clasificada en forma ascendente se sabe que ahí no va a estar el elemento, con lo que se moverá el apuntador de inicio que es LI a la posición siguiente a donde está el elemento central que esta apuntado por M. Procediendo a considerar esta nueva lista, que es la segunda mitad, como la nueva lista. + Que el elemento buscado ahora sea menor que el elemento apuntador por M, entonces, se desechará la segunda mitad de la lista y el apuntador que se actualizará será entonces LS, que es el que apuntaba al último elemento y ahora se moverá a una posición inmediata anterior a donde está apuntando M.

Búsqueda Binaria