C++ / algoritmo de busqueda binaria

Bienvenidos sean a este post, hoy veremos otra forma de busqueda.

En el post anterior vimos como crear un algoritmo de busqueda simple con iteradores para hacerlo completamente generico. La busqueda binaria puede ser mas simple que el visto anteriorrmente. Esto es asi porque el primer elemento que mira sera el de la mitad del contenedor. Si el elemento coincide con el que buscamos procede a devolver la posicion y finaliza con el algoritmo. En cambio, si el valor a buscar es menor que el del medio procede a trabajar con los valores de la izquierda de este. Por lo contrario, si es mayor al del medio procede a trabajar con los valores del lado derecho. En cualquiera de los casos, vuelve a repetir el proceso comparando el valor del medio del nuevo rango con el que buscamos. Y asi sucesivamente, hasta encontrar el valor o no. Para entenderlo vamos a analizar el siguiente codigo:

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
size_t buscar(const vector<T>& v, const T& e, int i, int f)
{
        if (i > f) return -1;
        int m = i + (f - i) / 2;
        if (v[m] == e)
                return m;
        if (v[m] > e)
                return buscar(v, e, i, m - 1);
        return buscar(v, e, m + 1, f);
}


int main(int argc, char **argv)
{
        vector<int> v{1,2,3,4,5,6,7,8,9,10};
        int res = buscar(v, 3, 0, v.size());
        if (res!= -1)
          cout << "Valor encontrado" << endl;
        else
          cout << "Valor no encontrado" << endl;

        return 0;
}

Para lograr lo comentado anteriormente se necesita implementar una funcion recursiva. Por esto nuestra funcion primero sera de tipo generica para poder trabajar cualquier tipo de dato pero buscara en un tipo vector. Y a su vez recibira tres valores mas, el primero sera el vector donde buscaremos, el siguiente sera el elemento a buscar y los ultimos dos seran para indicar el inicio y el final del segmento donde trabajaremos. Lo primero que haremos sea evaluar si la posicion inicial del segmento (i) es mayor a la del final (f), en caso de ser verdadero devuelve -1 porque el elemento informado no fue encontrado. Luego calcularemos el valor del medio del rango. Para ello sumaremos la posicion inicial a la diferencia entre la posicion final y la inicial, y la dividiremos por dos. Esto se encargara de establecer los segmentos a medida que no encuentre el valor. Tal como indicamos antes del ejemplo.

Con nuestro valor establecido lo pasamos como posicion del vector y lo comparamos con el valor informado, si son iguales devolvemos el valor de m para indicar que fue encontrado. De lo contrario, pasamos al siguiente condicional donde evaluamos si el valor del vector es mayor al informado. En caso de ser verdadero, trabajaremos con el rango de valores del lado izquierdo. Y para ello, haremos un llamado recursivo a la funcion pero pasaremos como valor de posicion final al valor de m-1 y repitiendo todo el proceso. En caso de no cumplirse ninguna de las dos condiciones anteriores, entendemos que el valor del vector es menor al informado. Por lo tanto, trabajaremos con el rango derecho de los valores. Y para poder trabajarlo, hacemos un llamado recursivo a la funcion pero pasaremos como posicion inicial al valor de m+1, y nuevamente repitiendo el proceso.

En el main, simplemente crearemos un vector con una serie de valores, para una mayor facilidad es preferible pasarlo ordenados, en una variable almacenaremos el resultado de llamar a la funcion buscar. A esta le pasamos el vector, el valor a buscar, la posicion inicial y la final. Para esta ultima usaremos a la funcion size para que pase el total de elementos que contiene. Luego tenemos un condicional donde si el valor devuelto y almacenado es distinto de -1 significa que fue encontrado y mostramos un mensaje en pantalla. En caso contrario, mostraremos el otro mensaje. Compilemos y veamos como es la salida:

$ ./buscar
Valor encontrado
$

Como pasamos un valor existente en la lista, nos lo indica en pantalla. Prueben de cambiarlo por un valor inexistente para verificar si lo encuentra. Nuevamente, al igual que sucedio en el post anterior esta es una funcion simple para realizar esa accion pero no es 100% generica. Porque si intentamos usar string u otro tipo nos devolvera un error de compilacion. Para solucionarlo, debemos usar a iteradores. Para ello debemos modificar el codigo de la siguiente manera:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
size_t buscar(const vector<T>& v, const T& e, int i, int f)
{
        if (i > f) return -1;
        int m = i + (f - i) / 2;
        if (v[m] == e)
                return m;
        if (v[m] > e)
                return buscar(v, e, i, m - 1);
        return buscar(v, e, m + 1, f);
}

int main(int argc, char **argv)
{
        vector<int> v{1,2,3,4,5,6,7,8,9,10};
        int res = binary_search(v.begin(), v.end(), 10);
        if (res != 0)
                cout << "Valor encontrador" << endl;
        else
                cout << "Valor no encontrador" << endl;


        return 0;
}

Como dijimos mas de una vez: para que vamos a reinventar la polvora, no? Porque la libreria algorithm, de la cual hablamos en este post, posee una funcion para realizar una busqueda binaria, binary_search, y esta trabaja de la forma correcta mediante objetos iterables. Tiene otras particularidades pero de eso hablaremos en un momento. Veamos como es el prototipo de la funcion en la libreria:

template <typename Iter, typename T>
bool binary_search(Iter start, Iter end, const T& elem);

Es muy similar a lo visto en la funcion buscar pero con una gran diferencia. La primera es que usamos un objeto iterador para el inicio y otro para el final, estableciendo asi el rango a trabajar, no es necesario pasar el objeto a trabajar y si pasamos el valor a buscar. Ya no es necessario que pasemos cual es el rango inicial para trabajar como haciamos con la funcion. La siguiente modificacion es eliminar el llamado a nuestra funcion, lo reemplazamos con binary_search donde pasaremos los valores de inicio y fin del vector, y el valor a buscar. En el condicional, en lugar de buscar que sea distinto a -1 le pasamos que sea a 0 pero el resto sigue siendo lo mismo. Si lo compilann y ejecutan deben obtener la misma salida que antes.

Inclusive, como hicimos en el post anterior, si cambian al vector por un list o en lugar de pasar datos de tipo int usamos a string, este seguira funcionando correctamente. Porque al manejar objetos iterables no tenemos limites de compatibilidad. Tambien tenemos otra ventaja, esta funcion no solo se limita a una busqueda de tipo secuencial sino que tambien se puede adaptar a una forma aleatoria si los valores no estan ordenados. Por esta razon, no siempre es necesario tener que desarrollar algo que ya existe en distintas librerias.

En resumen, hoy hemos visto a la busqueda binaria, primero hablamos sobre ella, luego vimos un ejemplo simple para entender el concepto, para luego ver la funcion que esta definida en la libreria algorithm. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.