Algoritmos de búsqueda

Un algoritmo de búsqueda es aquel que nos permite encontrar un elemento dentro de una estructura de datos como podría ser un vector o una base de datos.

Para explicar los dos algoritmos básicos de búsqueda, que son: la búsqueda secuencial y la búsqueda dicotómica o binaria; tomaremos como elemento un número entero y como estructura de datos un vector.

Algoritmo de búsqueda secuencial

Lo utilizaremos cuando nuestro vector esté desordenado. Se basa en ir recorriendo el vector, de manera "secuencial", hasta encontrar el elemento o hasta que lleguemos al final del mismo.

Este algoritmo no es muy eficiente, ya que tenemos que realizar muchas iteraciones. En el peor de los casos tendríamos que recorrer todo el vector, imagina que tuviera un millón de elementos!.

Un ejemplo de la implementación en C de este algoritmo sería así:

bool busqueda_secuencial(int v[], int N, int dato) {
   for(int i = 0; i < N; i++) {
      if(v[i] == dato) return true;
   }
   return false;
}

Algoritmo de búsqueda dicotómica o binaria

Uno de los requisitos para poder utilizar este algoritmo es que el vector esté ordenado. Se basa buscar en el elemento central del vector, si el elemento que buscamos es mayor, hacemos lo mismo con la parte alta del vector, y al revés si es menor. Este proceso se repite hasta que encontremos el elemento o hasta que ya no queden elementos en el vector. Este algoritmo es mucho más eficiente que el anterior, ya que, en comparación, reduce el número de iteraciones de manera exponencial. En contrapartida, el vector tiene que estar ordenado.

Un ejemplo de la implementación en C de este algoritmo sería así:

bool busqueda_dicotomica(int v[], int dato, int ini, int fin) {
   bool res;
   if(principio < fin) {
      int m = (ini + fin) / 2;
      if(dato < v[m])
         res = busqueda_dicotomica(dato, ini, m);
      else if(dato > v[m])
         res = busqueda_dicotomica(dato, m+1, fin);
      else
         res = true;
   } else res = false;
   return res;
}