¿Quién no ha jugado
alguna vez al juego de adivinar un número? Se trata de un juego muy
sencillo: el primer jugador piensa un número al azar, por ejemplo,
desde 1 hasta 100, y el segundo jugador tiene que adivinarlo. Para
ello va diciendo en voz alta distintos números, y el primer jugador
le dice si el número que ha pensado es mayor, o menor. La pregunta
es ¿cual es la mejor estrategia que podemos utilizar para adivinar
el número secreto en el menor número de intentos posibles? Una
posible estrategia, que funciona muy bien, sería decir como número
el punto intermedio del intervalo que nos queda por buscar. Si
hablamos de números desde 1 hasta 100, nuestro primer intento
debería ser el 50; supongamos que el número buscado es menor, en
este caso, y dado que el intervalo de búsqueda se ha reducido desde
1 hasta 50, nuestro segundo intento debería ser el 25, y así
sucesivamente.
Imaginemos ahora que el
departamente de recursos humanos de una determinada empresa tiene
almacenadas en un ordenador las fichas de todos sus empleados,
ordenadas alfabéticamente, y que desde la dirección necesitan una
ficha concreta. En este caso, ¿cual es el mejor algoritmo para
buscar la ficha deseada? A poco que pensemos un poco nos daremos
cuenta de que se trata exactamente del mismo problema que en el caso
anterior, y por tanto, ya tendríamos una estrategia de búsqueda
válida. Supongamos que lo que buscamos es la ficha del señor
Fernández, y que tenemos en total 1.000 fichas; por tanto
seleccionamos la ficha 500 (el punto intermedio) y vemos que
corresponde a la señora Jiménez, que según el orden alfabético es
mayor; el siguiente paso sería continuar con la búsqueda utilizando
las fichas desde la 1 hasta la 500. El algoritmo que implementa esta
estrategia se llama búsqueda binaria.
Veamos nuestro algoritmo de búsqueda binaria:
función búsqueda(A, x) p := 1 r := longitud(A) mientras p <= r hacer q := int((p+r)/2) si A[q] = x entonces retorna q si no si A[q]> x entonces r := q-1 si no p := q+1 fin si fin si fin para retorna NO_ENCONTRADO fin función
La función de búsqueda
recibe como primer parámetro un array de números enteros que han de
estar necesariamente ordenados, y como segundo parámetro el valor
que queremos encontrar en el array. Como salida nos devuelve la
posición (o índice) en la que dicho valor se encuentra dentro el
array, o la constante NO_ENCONTRADO
si es que el elemento no se ha encontrado. Lo primero que hacemos es
establecer los límites del intervalo en los que empieza nuestra
búsqueda, siendo p la
variable que contiene el valor menor (1 al empezar), y r
la variable que contiene el valor mayor (que al empezar es la
longitud del array, que viene determinada por la fución longitud()).
La función siguiría iterando mientras el intervalo de búsqueda
tenga una longitud mayor o igual que 1 (p<=r).
Para cada iteración del
bucle lo que hacemos es calcular la posición intermedia del
intervalo y comparamos su valor allí almacenado con el valor
buscado. Si ambos valores son iguales, hemos encontrado lo que
buscábamos y por tanto retornamos el índice. Si el valor es menor
modificamos el extremo inferior del intervalo, y si es mayor, el
extremo superior.
No hay comentarios:
Publicar un comentario