EVAP7

ALGORITMOS DE BÚSQUEDA

Disponemos básicamente de dos algoritmos para buscar información, según estén los datos desordenados u ordenados. En el primer caso, si no se dispone de información adicional sobre los datos, la posibilidad más directa es hacer una búsqueda secuencial. En el segundo caso, si los datos ya están ordenados, la forma más rápida de hacerlo es con una búsqueda binaria, que es una versión del ‘divide y vencerás’ dedicada a la búsqueda.

BÚSQUEDA SECUENCIAL
Imaginemos que queremos encontrar una clave determinada en el array de caracteres s[cont]. Basta hacer un barrido secuencial para encontrar la clave.
int busqueda_secuencial( char *s, int cont, char clave )
{
int t;
for( t=0 ; t<cont ; ++t )
if( clave = = s[t] ) return t;
return -1; /* cuando no se ha encontrado la clave */
}
El tiempo medio de búsqueda es de orden n/2.

BÚSQUEDA BINARIA
Si los datos están ordenados la búsqueda binaria es la más rápida que podemos hacer. Se comprueba el elemento mitad del array, si es mayor que la clave entonces se comprueba con el elemento mitad de la primera mitad, en caso contrario se comprueba con el elemento mitad de la otra mitad. Se repite el proceso de manera recursiva hasta encontrar el elemento clave o hasta verificar que no está en el array.
/* ejemplo: encontrar el 4 en el siguiente array */
1 2 3 4 5 6 7 8 9
1 2 3 4 
4
4
El código de esta función de búsqueda podría ser:
int busqueda_binaria( char *s, int cont, char clave )
{
int bajo, alto, medio;
bajo=0 ; alto = cont-1;
while( bajo <= alto )
{
medio = (bajo+alto)/2;
if( clave < s[medio] ) alto = medio-1;
else if ( clave > s[medio] ) bajo = medio+1;
else return medio; /* elemento encontrado */}
return -1;
}