Búsqueda Binaria

¿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.