UNIVERSIDAD NACIONAL DE CAJAMARCA

FACULTAD DE INGENIERÍA

ALGORITMOS Y ESTRUCTURA DE
DATOS I
Búsqueda
 Introducción

Métodos de búsqueda
¿Cómo busca google?

[Link]
¿Qué sabemos?

• ¿Qué es buscar?
• ¿Cómo buscamos?
• ¿Siempre buscamos de la misma
manera?
• ¿Qué tipos de búsqueda
conocemos?
• ¿Considera importante el orden al
realizar una búsqueda? ¿Por qué?
• ¿Qué tan a menudo realizamos una
búsqueda? ¿Son importantes?
¿Qué pasaría si?

• … nos piden verificar la existencia

de un valor cualquiera “x” en un
vector de 10 000 elementos,
cómo realizaríamos una
búsqueda de tal forma que se
minimice el número de
comparaciones?
Logro esperado

• Al término de la sesión, el
estudiante resuelve los
problemas propuestos,
empleando los conceptos
estudiados en el presente tema
verificando su planteamiento
como los resultados obtenidos.
Desarrollo del
tema
Búsqueda
Búsqueda

• La recuperación de información, es
una de las aplicaciones más
importantes de las computadoras.
• La búsqueda (searching) de
información está relacionada con
las tablas para consulta.
• El problema de búsqueda cae
naturalmente dentro de uno de los
dos casos:
– Si existen muchos registros, puede ser
necesario almacenarlos en dispositivos
como discos, externos a la memoria de
la computadora. Búsqueda externa.
– En el otro caso los registros que se
buscan se almacenan por completo
dentro de la memoria de la
computadora. Búsqueda interna
Búsqueda

• 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, fichero.
• Ejemplos típicos de búsqueda son:
localizar nombres y apellidos de un
alumno, localizar números de teléfono,
etc.
• Existen diferentes algoritmos de
búsqueda. El algoritmo elegido depende
de la forma en que se encuentren
organizados los datos.
• 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)
Búsqueda secuencial - Análisis

• Tiene el inconveniente del

consumo excesivo de tiempo en
INICIO la localización del elemento
designado.
Desde i=1 hasta n hacer
• Si no se encuentra, se verifican
si v[i]=x entonces los “n” elementos.
escribir “Elemento encontrado” • Si se encuentra en la lista podrá
fin_si ser el primero, el último o alguno
Fin_desde comprendido entre ambos.
FIN • El número medio de
comprobaciones es de
n +1
2
Búsqueda binaria

• La búsqueda binaria utiliza el método de divide y vencerás para localizar el valor

deseado.
• Esta requiere que los datos que se buscan estén clasificados en un determinado
orden.
• 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 determina si el elemento buscado está en la primera o la
segunda mitad de la lista y a continuación se repite este proceso, utilizando el
elemento central de esta sublista
Búsqueda binaria

Inicio Central Fin

2 3 4 5 6 7 8

4
Se encuentra en la primera mitad

I C F

Se encuentra en la segunda mitad

2 3 4
4
4
4
Búsqueda binaria

Inicio Central Fin

2 3 4 5 6 7 8

9
Se encuentra en la segunda mitad I C F

6 7 8
8
9
9 Se encuentra en la segunda mitad
Búsqueda binaria - Pseudocódigo

Leer x
Inicio  1
Fin  n
Centro  entero((inicio + fin)/2)
Mientras inicio <= fin y v[centro] <> x
Si x < v[centro]
fin  central-1
sino
inicio  centro + 1
Fin_si
Centro  entero((inicio + fin)/2)
Fin_mientras
Si x = v[centro]
entonces escribir “valor encontrado en” centro
sino escribir “valor no encontrado”
Fin Si
Análisis de la búsqueda binaria

• La búsqueda binaria es un método eficiente siempre que el vector esté

ordenado.
• En la práctica esto suele suceder, pero no siempre, por lo que es
necesario una ordenación previa del vector.
• Para obtener el número de comparaciones que realiza el algoritmo
consideremos un vector de 7 elementos.
• El número (N+1=8) se debe dividir en tres mitades antes de que se
alcance 1; es decir se necesita 3 comparaciones
• El medio matemático de expresar estos números es:

3 = log 2 8
Algoritmos de búsqueda recursiva

• Al igual que en el caso de los

algoritmos iterativos, consideraremos
dos casos respecto al estado de los
elementos sobre los cuales se desea
hacer la búsqueda: que no tengan
orden alguno y que estén ordenados
respecto a algún criterio.
Búsqueda secuencial

• Cuando hacemos una búsqueda función buscar (entero a[], entero n,

entero x)
sobre un arreglo del cual no inicio
tenemos más información que su si n = 0 entonces
tamaño, la idea general, como regresar 0
vimos anteriormente, es recorrer sino
todo el arreglo y detenerse si a[n] = x entonces
regresar n
cuando se encuentre el número x
si no
que se está buscando o cuando regresar buscar (a, n-1, x)
se haya verificado que x no iguala fin si
a algún elemento del arreglo. fin si
fin
Búsqueda recursiva

función buscar (entero a[], entero n,

entero x)
• Consideremos ahora el caso cuando los inicio
elementos del arreglo a están si n = 0 ∨ a[n] < x entonces
ordenados, digamos en forma regresar 0
ascendente. Al igual que en el caso sino
iterativo, podríamos aprovechar esta si a[n] = x entonces
propiedad e incluir una condición de regresar n
control con el fin de detener las si no
llamadas recursivas justo cuando el regresar buscar (a, n-1, x)
algoritmo descubra que no tiene caso fin si
buscar a x en cierta región del arreglo fin si
fin
Búsqueda

• La búsqueda binaria proporciona

un medio para reducir el tiempo
requerido para buscar en una
lista. Este método, sin embargo,
exige que los datos estén
ordenados. Existen otros
métodos que pueden aumentar
la velocidad de búsqueda en el
que los datos no necesitan estar
ordenados, este método se
conoce como transformación de
claves (clavedirección) o hashing.
Búsqueda mediante transformación de claves (hashing)

• El método de transformación de
claves consiste en convertir la
clave dada (numérica o
alfanumérica) en una dirección
(índice) dentro del array.
• La correspondencia entre las
claves y la dirección en el array se
establece por una función de
conversión (función o hash).
Transformación de claves

Colisión:
Métodos de transformación de claves - Truncamiento

• Ignora parte de la clave y se utiliza la parte restante

directamente como índice.
• Si las claves son enteros de ocho dígitos y la tabla de
transformación tiene mil posiciones, entonces el primero,
segundo y quinto dígitos desde la derecha pueden formar la
función de conversión. Por ejemplo, 72588495 se convierte en
895.
Métodos de transformación de claves - Plegamiento

• La técnica del plegamiento consiste en la partición de la clave en

diferentes partes y la combinación de las partes en un modo
conveniente (a menudo utilizando suma o multiplicación) para
obtener el índice.
• Un entero de ocho dígitos se puede dividir en grupos de tres, tres y
dos dígitos, los grupos se suman y se truncan si es necesario para
que estén en el rango adecuado de índices.
• Por consiguiente, si la clave es: 62538194 y el número de
direcciones es 100, la función de conversión será:
• 625 + 381 + 94 = 1100
• Que se truncará a 100 y que será la dirección deseada.
Métodos de transformación de claves -Aritmética modular

• Convierte la clave a un entero, divide por el tamaño del rango

del índice y toma el resto como resultado.
• h(x) = x mod m
• donde m es el tamaño del array con índices de 0 a m – 1. Los
valores de la función —direcciones— (el resto) irán de 0 a m –
1, ligeramente menor que el tamaño del array.
Métodos de transformación de claves - Mitad del cuadrado

• Este método consiste en calcular el cuadrado de la clave x. La función de

conversión se define como
– h(x) = c
• donde c se obtiene eliminando dígitos a ambos extremos de x2. Se deben utilizar
las mismas posiciones de x2 para todas las claves.
• Una empresa tiene ochenta empleados y cada uno de ellos tiene un número de
identificación de cuatro dígitos y el conjunto de direcciones de memoria varía en
el rango de 0 a 100. Calcular las direcciones de: 4205, 7148 y 3350

• x 4205 7148 3350

• x2 17 682 025 51 093 904 11 122 250
• Si elegimos, por ejemplo, el cuarto y quinto dígito significativo, quedaría
• h(x)= 82 93 22
Métodos de transformación de claves

• Colisiones
• La función de conversión h(x) no siempre proporciona valores distintos,
puede que se obtenga la misma dirección (colisión) y se debe encontrar
métodos para su solución.
• Los ejemplos vistos anteriormente de las claves DNI correspondientes al
archivo de empleados, en el caso de cien posibles direcciones. Si se
considera el método del módulo en el caso de las claves, y se considera el
número primero 101
• 123445678 123445880 proporcionarían las direcciones:
• h (123445678) = 123445678 mod 101 = 44
• h (123445880) = 123445880 mod 101 = 44
Recordemos lo
aprendido
Revisando algunos conceptos

• ¿Qué tipos de búsqueda

conocemos?
• ¿En qué consiste la búsqueda
binaria?
• ¿Qué entendemos por tablas hash?
• ¿Qué métodos de transformación
de claves tenemos?
• ¿Describa en qué consiste cada
método?
• ¿Qué es un colisión?
• ¿Cómo podemos resolver una
colisión?

Aplicando lo
aprendido
 Ejercicios de aplicación
• Realizar una búsqueda binaria de un listado de • Los números empleados —campo clave— de
n nombres y apellidos ingresados por consola. una empresa constan de cuatro dígitos y las
• Realizar una búsqueda recursiva de un listado direcciones reales son 100. Se desea calcular
de países que hemos ingresado a través del las direcciones correspondientes por el
teclado método de plegamiento de los empleados.
• Buscar un curso dentro de un arreglo de (4205, 8148 y 3355)
cursos.
• Un vector T tiene cien posiciones, 0..100.
Supongamos que las claves de búsqueda de los
elementos de la tabla son enteros positivos
(por ejemplo, número del DNI). Utilizando
aritmética modular encontrar su posición en el
arreglo.