UNIVERSIDAD NACIONAL DE CONCEPCIÓN
FACULTAD DE CIENCIAS ECONOMICAS Y ADMINISTRATICAS
ALGORITMIA III
ING. SERGIO RODRÍGUEZ ENCINA
ALGORITMOS DE BUSQUEDA
INTRODUCCIÓN
La recuperación de información, como ya se ha comentado, es una de las aplicaciones más
importantes de las computadoras. La búsqueda (searching) de información está relacionada con
las tablas para consultas (lookup). Estas tablas contienen una cantidad de información que se
almacena en forma de listas de parejas de datos. Por ejemplo, un diccionario con una lista de
palabras y definiciones; una lista de estudiantes y sus notas; un índice con títulos y contenido de
los artículos, etc. En todos estos casos es necesario con frecuencia buscar un elemento en una
lista.
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 clave 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
1
sustancial en el rendimiento del programa.
INTRODUCCIÓN
El problema de búsqueda cae naturalmente dentro de los dos casos típicos ya
tratados. Si existen muchos registros, puede ser necesario almacenarlos en archivos
de disco o cinta, externo a la memoria de la computadora. En este caso se llama
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, 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.
2
INTRODUCCIÓN
Existen diferentes algoritmos de búsqueda. El algoritmo elegido depende de la forma
en que se encuentren organizados los datos.
La operación de búsqueda de un elemento N en un conjunto de elementos consiste
en:
• Determinar si N pertenece al conjunto y, en ese caso, indicar su posición en él.
• Determinar si N no pertenece al conjunto.
Los métodos más usuales de búsqueda son:
• Búsqueda secuencial o lineal.
• Búsqueda binaria.
• Búsqueda por transformación de claves (hash).
3
BUSQUEDA- SECUENCIAL
La búsqueda secuencial busca un elemento de una lista utilizando un valor destino
llamado clave. En una búsqueda secuencial (a veces llamada búsqueda lineal), los
elementos de una lista se exploran (se examinan) en secuencia, uno después de otro.
El algoritmo de búsqueda secuencial compara cada elemento del array con la clave
de búsqueda. Dado que el array no está en un orden prefijado, es probable que el
elemento a buscar pueda ser el primer elemento, el último elemento o cualquier otro.
De promedio, al menos el programa tendrá que comparar la clave de búsqueda con
la mitad de los elementos del array. El método de búsqueda lineal funcionará bien
con arrays pequeños o no ordenados.
4
BUSQUEDA- SECUENCIAL
EJEMPLO
Se 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
'Elemento encontrado' y otro que diga 'posición = ‘. Si existen n elementos, se
requerirán como media n/2 comparaciones para encontrar un determinado elemento.
En el caso más desfavorable se necesitarán n comparaciones.
5
BUSQUEDA- SECUENCIAL
Método 1
algoritmo busqueda_secuencial_1
//declaraciones
inicio
llenar (A,n)
leer(t)
//recorrido del vector
desde i ← 1 hasta n hacer
si A[i] = t entonces
imprimir('Elemento encontrado’)
imprimir('en posicion', i)
fin_si
fin_desde
6
fin
BUSQUEDA- SECUENCIAL
Consideraciones sobre la búsqueda lineal
El método de búsqueda lineal tiene el inconveniente del consumo excesivo de tiempo en la localización
del elemento buscado. Cuando el elemento buscado no se encuentra en el vector, se verifican o
comprueban sus n elementos.
En los casos en que el elemento se encuentra en la lista, el número podrá ser el primero, el último o
alguno comprendido entre ambos. Se puede suponer que el número medio de comprobaciones o
comparaciones a realizar es de (n+1)/2 (aproximadamente igual a la mitad de los elementos del vector).
La búsqueda secuencial o lineal no es el método más eficiente para vectores con un gran número de
elementos.
En estos casos, el método más idóneo es el de búsqueda binaria, que presupone una ordenación previa
en los elementos del vector. Este caso suele ser muy utilizado en numerosas facetas de la vida diaria. Un
ejemplo de ello es la búsqueda del número de un abonado en una guía telefónica; normalmente no se
busca el nombre en orden secuencial, sino que se busca en la primera o segunda mitad de la guía; una
vez en esa mitad, se vuelve a tantear a una de sus dos submitades, y así sucesivamente se repite el
proceso hasta que se localiza la página correcta. 7
