Métodos de Búsqueda.

La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo Secuencial y Binaria.

Método de Búsqueda Secuencial:

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.
Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Supongamos que una lista de elementos almacenados en un vector (array unidimensional). El método sencillo de buscar un elemento en un vector es explorar secuencialmente el vector, o dicho entre otras palabras recorrer el vector desde el primer elemento hasta el último. Si se encuentra el elemento buscado visualizar un mensaje similar a ‘fin de búsqueda’, en caso contrario visualizar un mensaje similar a ‘elemento no existe en la lista’.
En otras palabras, la búsqueda secuencial compara cada elemento del vector con el valor deseado, hasta que este se encuentra o se termina de leer el vector completo. La búsqueda secuencial no requiere ningún requisito por parte del vector y, por consiguiente, no necesita estar ordenado. El recorrido del vector se realizará normalmente con estructuras repetitivas.

Método de Búsqueda Binaria:

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.
Esta búsqueda 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 este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

En una búsqueda secuencial se comienza con el primer elemento del vector y se busca en el hasta que se encuentra el elemento deseado o sea alcanza el final del vector.
Aunque este puede ser un método adecuado para pocos datos, se necesita una técnica más eficaz para conjuntos grandes de datos.
Si el número de elementos del vector es grande, el algoritmo de búsqueda lineal se ralentizaría en tiempo de un modo considerable. Por ejemplo, si tuviéramos que consultar un nombre en la guía telefónica de una gran ciudad, como Madrid, con una cifra aproximada de un millón de abonados, el tiempo de búsqueda, según el nombre se podría eternizar naturalmente, las personas que viven en esa gran ciudad nunca utilizarán un método de búsqueda secuencial, sino un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades hasta encontrar el elemento buscado.
Si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina Búsqueda 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 este es el elemento buscado, entonces la búsqueda ha terminado. En caso contrario, se determina si el elemento buscado está en la primera o en la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sublista.
El proceso de búsqueda debe terminar normalmente conociendo si la búsqueda ha tenido éxito (se ha encontrado el elemento o bien no ha tenido éxito) no se ha encontrado el elemento, normalmente se deberá devolver la posición del elemento buscado dentro del vector.