C++ / algoritmo de busqueda

Bienvenidos sean a este post, hoy veremos un algoritmo de los contenedores STL.

En este post hablamos sobre la libreria algorithm y algunos de los algoritmos que posee para poder realizar algunas tareas en nuestros contenedores. En este otro post mencionamos que los algoritmos a su vez no dejan de ser funciones que trabajan con colecciones, donde reciben a la informacion, la procesan y devuelven el resultado del procesamiento. Con este breve comentario mas lo que ya hemos visto de contenedores, pasemos a crear un algoritmo de busqueda simple. Para ello analicemos el siguiente ejemplo:

#include <iostream>
#include <vector>

template <typename T>
int buscar(const std::vector<T>& v, const T& elem)
{
        for(int i=0; i < v.size(); i++)
        {
                if (v[i] == elem)
                        return i;
        }
        return -1;
}

int main(int argc, char **argv)
{
        std::vector<int> vec{1, 10, 2, 20, 3, 30, 4, 11, 6, 10, 5, 99};
        int res = buscar(vec, 30);
        if (res!= -1)
          std::cout << "Valor encontrado" << std::endl;
        else
          std::cout << "Valor no encontrado" << std::endl;

        return 0;
}

Primero deffiniremos una funcion generica llamada buscar, la cual recibira un vector y el otro argumento sera el elemento que buscaremos en el vector. En este bloque, pasaremos por todos los elementos y cuando coincidamos el elemento del vector con el informado devolveremos la posicion del mismo. En caso de no haber coincidencia, nos devuelve el valor -1 para indicar que no fue encontrado.

En el main, primero creamos un vector con varios valores, y luego hacemos un llamado a la funcion donde pasamos el vector anterior y un valor a buscar. Lo siguiente es un condicional donde verificamos si el valor devuelto es distinto a -1. En caso de ser verdadero, muestra un mensaje indicando que fue encontrado. En caso contrario, indicamos lo contrario. Compilemos y veamos como es la salida:

$ ./buscar
Valor encontrado
$

Esta algoritmo nos permite saber si un valor se encuentra en el listado de un vector. Pero esta puede tener tres casos distintos y varia su performance. El primero y mejor caso seria cuando encuentra el valor en la primera posicion porque dara la informacion inmediatamente. El segundo caso sera entre el inicio y el fin, siendo el mas promedio porque es la mayor probabilidad donde puede ubicarse el dato a buscar. Y el tercer caso, y el peor de ellos, sera cuando no se encuentre o sea la ultima posicion del vector. Dado que debera pasar por todos los elementos hasta encontrarlo o no. Y como este tiene un valor N de elementos para buscar, cuando mas elementos debe procesar mas tiempo tardara.

Con todo lo comentado anteriormente y en otos posts, podemos decir que la esencia de STL es conectar contenedores y algoritmos mediante iteradores. Como el algoritmo anterior es secuencial no se lo considera compatible con STL. Esto principalmente por las restricciones estrictas que posee en los parametros de entrada. Por esta razon, el algoritmo anterior no es 100% generico. Cambiemos el codigo anterior de la siguiente manera:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename T>
int buscar(const vector<T>& v, const T& elem)
{
        for(int i=0; i < v.size(); i++)
        {
                if (v[i] == elem)
                        return i;
        }
        return -1;
}

int main(int argc, char **argv)
{
        vector<string> vec{"hola","mundo","tinchicus","argentina"};
        int res = buscar(vec, 30);
        if (res!= -1)
          cout << "Valor encontrado" << endl;
        else
          cout << "Valor no encontrado" << endl;

        return 0;
}

En este caso, tenemos el mismo codigo pero la unica modificacion que hicimos es en vector donde tendremos valores de tipo string, y aplicamos un namespace para simplificar el nombre de los llamados. Si lo compilamos sucedera lo siguiente:

$ g++ buscar.cpp -o buscar
buscar.cpp: In function ‘int main(int, char**)’:
buscar.cpp:21:25: error: no matching function for call to ‘buscar(std::vector<std::__cxx11::basic_string<char> >&, int)’
   21 |         int res = buscar(vec, 30);
      |                   ~~~~~~^~~~~~~~~
buscar.cpp:8:5: note: candidate: ‘template<class T> int buscar(const std::vector<T>&, const T&)’
    8 | int buscar(const vector<T>& v, const T& elem)
      |     ^~~~~~
buscar.cpp:8:5: note:   template argument deduction/substitution failed:
buscar.cpp:21:25: note:   deduced conflicting types for parameter ‘const T’ (‘std::__cxx11::basic_string<char>’ and ‘int’)
   21 |         int res = buscar(vec, 30);
      |                   ~~~~~~^~~~~~~~~
$

Como mencionamos, esta funcion no es un algoritmo 100% generico. Para ello, debemos modificar el codigo anterior de la siguiente manera:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename Iter, typename T>
int buscar(Iter p, Iter u, const T& e)
{
        for(size_t i = 0; p != u; p++, ++i )
        {
                if (*p == e)
                        return i;
        }
        return -1;
}

int main(int argc, char **argv)
{
        vector<string> v{"hola","mundo","tinchicus","argentina"};
        int res = buscar(v.begin(), v.end(), "tinchicus");
        if (res!= -1)
          cout << "Valor encontrado" << endl;
        else
          cout << "Valor no encontrado" << endl;

        return 0;
}

La unica modificacion la hicimos en la funcion buscar. Modificamos al template para que tenga dos valores genericos. El primero sera para el objeto iterador y el siguiente para el elemento a buscar. En la funcion ahora tendremos tres argmentos; el primero sera para el origen del iterador, el segundo sera para el final del iterador, y el tercero sera para el valor que buscaremos. En el bucle usaremos al tipo size_t para crear el objeto que usaremos para contar. Esto lo hara mientras la primera posicion sea distinta de la ulttima, e incrementaremos al objeto de la posicion original para pasar al siguiente elemento y el contador para hacer el seguimiento de los valores. En el bloque tenemos un condicional donde si el puntero de la posicion del contenedor es igual al elemento recibido devolvemos la posicion. En comparacion con el codigo anterior, ahora al llamar a la funcion pasamos los valores de los metodos begin y end para generar el ciclo de busqueda. Compilemos y veamos como es la salida:

$ ./buscar
Valor encontrado
$

Ahora si tenemos un algoritmo 100% generico e inclusive pueden manejar hasta otros contenedores. Tomen esta linea:

vector<string> v{"hola","mundo","tinchicus","argentina"};

Y hagan el siguiente cambio:

list<string> v{"hola","mundo","tinchicus","argentina"};

Si lo cambiamos por una list, no se olviden de agregar la libreria, lo compilan y ejecutan deben obtener la misma salida que antes. Y demostrando lo que comentamos, que el uso de los iteradores nos permite un mejor uso de funciones sobre nuestros contenedores. Este es el primer algoritmo que hablamos pero en los proximos posts ahondaremos en otros.

En resumen, hoy hemos visto como crear un algoritmo de busqueda, desde su forma mas simple con una compatibilidad basica, pero luego vimos como mejorarlo con iteradores. 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.