Estructura de Datos:
algoritmo de búsqueda
Ing. Ana Maria Caviedes Castillo
Ingeniería de software y computación
lV semestre
Corporación universitaria autónoma del cauca
Facultad de ingeniería
Algoritmo de búsqueda
Surgen de la necesidad de conocer tanto si
un dato se encuentra o no dentro de una
colección como de la posición que ocupa.
A menudo un programador estará trabajando
con grandes cantidades de datos almacenados
en arreglos y pudiera resultar necesario
determinar si un arreglo contiene un valor
que coincide con algún valor clave o
buscado.
Algoritmo de búsqueda
Existen diferentes algoritmos de
búsqueda y la elección depende de la
forma en que se encuentren organizados
los datos: si se encuentran ordenados o
si se ignora su disposición o se sabe
que están al azar. También depende de
si los datos a ordenar pueden ser
accedidos de modo aleatorio o deben ser
accedidos de modo secuencial.
Algoritmo de búsqueda
Es una operación para encontrar la posición de un
elemento entre un conjunto de elementos dados: lista,
tabla o archivo
Búsqueda(vector, elemento):
i∈{1,....,n} si existe tal elemento
0 en otro caso
Algoritmos de búsqueda:
– Búsqueda secuencial
– Búsqueda secuencial ordenada
– Búsqueda binaria
Búsqueda secuencial
Es el algoritmo de búsqueda más simple, menos eficiente y que
menos precondiciones requiere: no requiere conocimientos sobre
el conjunto de búsqueda ni acceso aleatorio.
Consiste en comparar cada elemento del conjunto de búsqueda con
el valor deseado hasta que éste sea encontrado o hasta que se
termine de leer el conjunto.
❖ Recorrer uno por uno los elementos.
❖ Comparar según sea el criterio.
❖ Se puede querer recuperar el valor o en la posición.
❖ Tiene un orden αn
Búsqueda secuencial
Búsqueda secuencial
❖ En arreglos bidimensionales el algoritmo
es similar.
❖ Se puede hacer por filas o por columnas.
❖ Esta decisión puede afectar el rendimiento
❖ Por lo general, preferir por filas.
❖ Tiene dos condiciones de finalización:
▪ Cuando se encuentra el valor
▪ Cuando se termina de leer por completo
el listado
Búsqueda secuencial
int bisecuencial_search(int numeros[][N], int
valor){
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(numeros[i][j]==valor)
return i*N+j;
return -1;
}
…
pos = bisecuencial_search(binumeros, 11);
if(pos>=0)
printf("bisec) numeros[%d][%d] = %d\n",
pos/N,pos%N,
binumeros[pos/N][pos%N]);
Búsqueda secuencial
Ventajas
• Es sencillo de implementar ya que únicamente
se utilizan estructuras repetitivas. (Hasta
aproximadamente 500 elementos)
• No requiere que el listado esté ordenado o en
algún estado especial.
Desventajas
• Es poco eficiente ya que se debe recorrer por
completo el arreglo. (muy lento)
• Tiempo excesivo de procesamiento en vectores
grandes.
• Se requieren (N+1)/2 comparaciones promedio
• En el peor de los casos se requiere N
comparaciones.
Búsqueda secuencial
Mejoras del algoritmo
• El algoritmo realiza dos comparaciones en cada
iteración:
✓ Una para comparar si se encuentra el elemento t
✓ La otra para evaluar si ya se llego al final del
arreglo
• Se puede mejorar el rendimiento disminuyendo a una
comparación por iteración al agregar un “valor
centinela” que permita descubrir si ya se terminado de
recorrer el arreglo.
• Se utiliza el valor buscado como valor centinela y se
coloca al final del arreglo (en una posición adicional)
para forzar a que el algoritmo siempre tenga éxito
encontrando el valor buscado
Búsqueda secuencial
Búsqueda con centinela
Si tuviésemos la seguridad de que el
elemento buscado está en el conjunto, nos
evitaría controlar si se supera el límite
superior. Para tener esa certeza, se
almacena un elemento adicional (centinela),
que coincidirá con el elemento buscado y
que se situará en la última posición del
arreglo de datos. De esta forma se asegura
que encontraremos el elemento buscado.
Búsqueda secuencial
Búsqueda con centinela
Búsqueda Binaria
La búsqueda binaria es el método, donde si el arreglo esta
bien ordenado, se reduce sucesivamente la operación
eliminando repetidas veces la mitad de la lista restante.
El proceso comienza comparando el elemento central del
arreglo con el elemento buscado.
Si ambos coinciden finaliza la búsqueda.
Si no ocurre así, el elemento buscado será mayor o menor en
sentido estricto que el elemento central del arreglo.
Si el elemento buscado es mayor se procede a hacer búsqueda
binaria en el sub-arreglo superior, si el elemento buscado
es menor que el contenido de la casilla central, se debe
cambiar el segmento a considerar al segmento que está a la
izquierda de tal sitio central.
Búsqueda Binaria
Este método se puede aplicar tanto a datos en listas lineales
como en árboles binarios de búsqueda. Los prerrequisitos para
la búsqueda binaria son:
▪ La lista debe estar ordenada, en un orden
especifico de acuerdo al valor de la clave.
▪ Debe conocerse el número de elementos.
▪ Si el conjunto de elementos es grande, el
tiempo de búsqueda se puede reducir utilizando
el siguiente algoritmo de tipo divide y
vencerás:
▪ Se divide el elemento en dos partes.
▪ Se determina la parte que debe contener la
clave buscada.
▪ Se repite el proceso en esa parte.
Búsqueda Binaria
❖ Una forma razonable de dividir el
conjunto de elementos ordenados y
después utilizar los índices del
arreglo ordenado para determinar la
parte del arreglo sobre la que se va
a trabajar.
❖ Muy rápida
❖ Requiere datos ordenados
❖ No sirve para recuperar la posición
Búsqueda binaria
Búsqueda binaria
Ventajas
• Se puede aplicar tanto a datos en listas
lineales como en árboles binarios de
búsqueda.
• Es el método más eficiente para encontrar
elementos en un arreglo ordenado..
Desventajas
• Este método funciona solamente con
arreglos ordenados, por lo cual, si nos
encontramos con arreglos que no están en
orden, este método, no nos ayudaría en
nada.
Búsqueda binaria
Búsqueda
1. Realice un programa que adivine un número un número entre 1
y 100.(Use búsqueda binaria) para lo cual cuenta con 7
oportunidades de adivinar como máximo. Indique en cual de las
oportunidades lo adivina.
2. Realice un programa que inicialice un arreglo de tamaño n y lo
ordene (use cualquier método de ordenamiento) y adicionalmente
lea un número para buscarlo en el arreglo. Determine si el
número se encuentra o no en el arreglo. Si se encuentra imprima
la posición (Use búsqueda binaria)
