Algoritmos Busqueda

ALGORITMO DE
BÚSQUEDAS

Ana María Marín Rueda – 20101235088
Tirso Alejandro Sarmiento Hernández -

ALGORITMOS DE
BÚSQUEDA
La búsqueda de valores es una operación
de vital importancia, cuando semanipula
conjunto de datos. Este permite la
recuperación de datos previamente
almacenados.

Los métodos de búsqueda tienen por
objeto la localización de un elemento (en
un conjunto de datos) elcual se distingue
por el valor de una clave. El tipo de
búsqueda puede clasificarse como
interna o externa.
clave= valor que caracteriza en forma
unívoca al elemento

Estos algoritmos tienen dosfinalidades:


Determina si el elemento buscado se
encuentra en el conjunto en el que se
busca



Si el elemento está en el conjunto, hallar
la posición donde se encuentra.

TIPOS DE BÚSQUEDASECUENCIAL








Es el más simple de los algoritmos de
búsqueda.
Consiste en recorrer el arreglo
comparando cada el elemento accedido
contra la clave buscada.
Este algoritmo se puede optimizarcuando el array esta ordenado (array:)
La búsqueda puede realizarse en arreglos
ordenados o desordenados.

EJEMPLO
int buscar (int clave, int datos [ ], int n)
{
int i;
i = 0;
while ( (i < n) &&(datos[ i ] != clave) )
i = i + 1;
return i;
}

BINARIA O DICOTÓMICA


Es más eficiente para encontrar
elementos en un arreglo.



El array debe estar ordenado.



Compara el elemento con elvalor
buscado.



Si ambos coinciden, o no se encuentra el
elemento buscado, finaliza la búsqueda.

EJEMPLO
int buscar (int clave, int datos [ ], int n)
{
int inferior, superior, centro;
inferior =0;
superior = n-1;
while ( (inferior < = superior) )
{
centro = (inferior + superior )/ 2; /*división entera */
if ( clave == datos [ centro ] )
return centro; /* encontrado */
else
if (clave < datos[centro ] )
superior = centro - 1; /* buscar en la primera mitad */
else
inferior = centro + 1; /* buscar en la segunda mitad */
}
/* si no lo encuentra, retorna “n” */
return n;
}

FIN...