Busquedas

Búsqueda

La recuperación de información, como ya se ha comentado, es una de las aplicaciones mas importantes de las computadoras

La búsqueda (searching) de información esta relacionada con las tablas para consultar (lookup). Esta tablas contienen una cantidad de información que se almacena en forma de lista de parejas de datos. Por ejemplo, un diccionario con una lista de palabras y definiciones; un catalogo con una lista de libros de informática; una lista de estudiantes y sus notas; un índice con títulos y contenido de los artículos publicados es una determinada revista, etc. En todos estos casos es necesario con frecuencia buscar un elemento en una lista.

Una vez que se encuentra el elemento, la identificación de su información correspondiente es un problema menor. Por consiguiente, nos centraremos en el proceso de búsqueda. Supongamos que se desea buscar el vector X [1]..X[n], que tiene componentes numéricos, para ver si contiene o no un numero dado T

Si en vez de tratar sobre vectores se desea buscar información en un archivo, debe realizarse la búsqueda a partir de un determinado campo de información denominado campo clave. Así, en el caso de los archivos de empleados de una empresa, el campo claves puede ser el número de DNI o los apellidos.

La búsqueda por claves para localizar registros es, con frecuencia, una de las acciones que mayor consumo de tiempo conlleva y, por consiguiente, el modo en que los registros están dispuestos y la elección del modo utilizado para la búsqueda pueden redundar en una diferencia sustancial en el rendimiento del programa.

El programa de búsqueda cae naturalmente dentro de los dos casos típicos ya tratados. Si extienden muchos registros, puede ser necesario almacenarlos en archivos de discos o cinta, externo a la memoria de la computadora. Este caso se denomina búsqueda externa. En el otro caso, los registros que se buscan se almacenan por completo dentro de la memoria de la computadora. Este caso se denomina búsqueda interna.

En la práctica, en la búsqueda se refiere a la operación de encontrar la posición de un elemento entre un conjunto de elementos dados: lista, tabla o fichero.

Ejemplos típicos de búsqueda son localizar nombre y apellido de un alumno, localizar números de teléfono de una agenda, etc

Existen diferentes algoritmos de busqueda. El algoritmo elegido depende de la forma en que se encuentren organizados los datos.

La operación de busqueda de un elemento N en un conjunto de elementos consiste en:

• Determinan si N pertenece al conjunto y, en caso, indicar su posición en el,

• Determinar si N no perteneces al conjunto

Los métodos mas usuales de búsqueda son:

• Búsqueda secuencial o lineal

• Búsqueda binaria

• Búsqueda por trasformación de claves (hash)

Búsqueda secuencial

Supongamos una lista de elementos almacenados en un vector (arraya unidimensional). El método mas sencillo de buscar un elemento en un vector es explorar secuencialmente el vector o, dicho en otras palabras, recorre el vector desde el primer elemento al ultimo. Si se encuentra el elemento buscado, visualizar un mensaje similar a “fin de búsqueda” ;en caso contrario, visualizar un mensaje similar a ”el elemento no existe en la lista”.

en otras palabras, la busqueda secuencial compara cada elemento del vector con el valor deseado, hasta que este se encuentra o termina de leer el vector completo.

La busqueda secuencial no requiere ningún requisito por parte del vector y, por consiguiente, no necesitaba estar ordenado. El recorrido del vector se realiza normalmente con estructuras respectivas

Ejemplo

Si tiene un vector A que contiene n elementos numéricos (N) >=1(A [1], A[2], A[3], …, A[n]) y se desea buscar un elemento dado t. si el elemento t se encuentra, visualizar un mensaje “el elemento encontrado” y otro que diga “posición=”

Si existe n elementos, se requieran como media n/2 comparaciones para encontrar un determinado elemento. En el caso más desfavorable se necesitara n comparaciones.

Método 1:

Algoritmo busqueda_secuanecial_1

Inicio

Leer (t)

//recorrido del vector

Desde i  1 hasta n hacer

Si A[i] = t entonces

Escribir (“el elemento encontrado”)

Escribir (“en posición” , i)

Fin_si

Fin_desde

Fin

Método 2:

Algoritmo búsqueda_secuencial_2

Inicio

Leer (t)

I  1

Mientras (A[i]) <> t) y (i =< n) hacer

I  i + 1

//este bucle se detiene bien con A[1] = t o bien i >n

Fin_mientras

Si A [i] = t entonces //condición de parada

Escribir (“el elemento se ha encontrado en la posición”, i)

Si_no //recorrido del vector terminado

Escribir (“el numero no se encuentra en el vector”)

Fin_si

Fin

Este método no es completamente satisfactorio, ya que si t no esta en el vector A, i toma el valor n+1 y la comparación

A [i ] <> t

Producirá una referencia al elemento A[n+1], que presumiblemente no existe. Este problema se resuelve sustituyendo i =< n por i<n en la instrucción mientras, es decir, modificando la instruccio anterior mientras por

Mientras (A[i] <> t) y (i < n) hacer

Método 3:

Algoritmo busqueda_secuencial_3

Inicio

Leer (t)

I  1

Mientras (A[i] <> t) y (i < n) hacer

I  i + 1

//este bucle se detiene cuando A [i] = t o i >= n

Fin_mientras

Si A[i] = t entonces

Escribir (“el numero deseado esta presente y ocupa el lugar”, i)

Si_no

Escribir (t, “no existe en el vector”)

Fin_si

Fin

Método 4:

Algoritmo busqueda_secuecial_4

Inicio

Llamar_a llenar (A)

Leer (t)

I  1

Mientras i <=n hacer

Si t = A[i] entonces

Escribir (“se encontró el elemento buscado en la posición”,1)

Fin-si

Ii+1

Fin _mientras

Fin

Busqueda secuencial con centinela

Una manera muy eficaz de realizar una busqueda secuencial consiste en modificar los algoritmos anteriores utilizando un elemento centinela. Este elemento se agrega al vector al final del mismo. El valor del elemento centinela es el del argumento. El propósito de este elemento centinela, A[n + |], es significar que la busqueda siempre tendrá existo. El elemento A[ n + 1] sirve como centinela

...