El algoritmo de búsqueda dicotómica es una manera muy eficiente de realizar búsquedas en una lista, siempre y cuando sus elementos se encuentren ordenados.

No obstante, en algunos casos se utiliza en contextos que hacen que pierda su eficiencia comportándose incluso peor que una búsqueda secuencial. En este artículo describimos el fundamento de la búsqueda dicotómica y reflexionamos acerca de estas situaciones "peligrosas".

Por supuesto, también proponemos una implementación sencilla de este tipo de búsqueda.

Este algoritmo acepta como entrada una lista (llamémosle v) de valores ordenados, junto con un valor que queremos comprobar si está en la lista (llamémosle b).

El algoritmo busca en la lista v el valor b, y si lo encuentra devolverá la posición de b dentro de la lista l. Si no lo encuentra, debe indicarlo de alguna manera.

Antes de meternos en harina, vamos a reflexionar un poco acerca de las implicaciones que tiene utilizar este algoritmo. Vamos a pensar en una lista de valores que se puedan ordenar por algún criterio... Da igual que sean enteros, cadenas, reales, fechas, coches, perros... el caso es que se puedan ordenar. Utilizaremos enteros, ya que estamos muy familiarizados con el orden que mantienen.

Por ejemplo, tomemos esta lista:

7, 4, 33, 18, 15, 20, 19, 26, 5

Los elementos en la lista siguen una secuencia... El 7 está en la primera posicion, el 4 en la segunda... etc... Sin embargo, no tienen orden.

Bien... supongamos que quiero saber si el número 20 está en la lista, y si es así, qué posición ocupa. ¿Para qué? Bueno... en este caso puede que tenga poco sentido. Sólo es un ejemplo, pero imagina que los elementos de la lista no son un simple entero, sino un objeto, o una estructura o registro que representa a un coche, con su matrícula y un montón más de características. Hacer una búsqueda ahí por matricula tiene más sentido ¿no?

Vale... pero volvamos al 20. Para saber si está en la lista, como no tiene orden, lo más sencillo, aparentemente es realizar una búsqueda secuencial. Es decir, comparar el número que busco (20) con el primer elemento. Si es igual, ya lo he encontrado, si no, paso al segundo elemento y repito... y así hasta que lo encuentre o hasta que haya recorrido toda la lista. Si no lo encuentro, lo indicaré de alguna manera.

Este tipo de búsqueda tiene una complejidad lineal, del orden O(n) siendo n el tamaño de la lista, es decir, el tiempo que tarda en realizarse en el peor caso crece proporcionalmente con el tamaño de la lista.

Sin embargo, si la lista está previamente ordenada antes de comenzar, podemos aplicar la estratégia de la búsqueda binaria o dicotómica.

Cojamos la misma lista de antes pero ordenada.

 4, 5, 7, 15, 18, 19, 20, 26, 33

Seguimos buscando el 20, pero ahora sabemos que la lista está ordenada. La estrategia es similar a la que utilizamos cuando buscamos una palabra en un diccionario gordo: como el diccionario tiene las palabras ordenadas, nunca lo abrimos por la primera hoja... lo abrimos aproximadamente por la mitad, y si la palabra que estamos buscando está antes que las palabras de la hoja que nos ha salido, volvemos a repetir la operación con la primera mitad de hojas. Si está después, lo hacemos con la segunda mitad. Es decir, vamos dando saltos porque el hecho de que las palabras estén ordenadas nos lo permite.

Hagamos lo mismo con la lista de arriba. Vamos a comparar el 20 con el elemento que está exactamente en la mitad de la lista (para saber cual es, hagamos unos pocos cálculos: el primer elemento está en la posición 1, y el último en la 9... la posición intermedia será (9+1)/2... es decir, el 5º... ese es el número 18. Como el que buscamos es mayor (el 20) y la lista está ordenada, ya sé que el 20 no está en el quinto lugar ni en los anteriores. 

4, 5, 7, 15, 18, 19, 20, 26, 33

Ahora consideraré del 6º al 9º. El que queda enmedio es (6+9)/2, es decir 7. Compruebo si el 7º elemento es el que busco... Anda... pues sí... Así que ya he llegado.

La gracia es que cada vez que comparo el elemento que busco con el el de enmedio del intervalo que estoy considerando y no es el que busco, elimino la mitad del intervalo de búsqueda. Eso está muy bien, porque significa que en el peor caso (que el número que busco no este en el vector) realizo log₂n veces la comparación... es decir, el algoritmo tiene una complejidad logarítimica. La verdad es que parece muy atractivo, y seguro que en muchas ocasiones nos sentimos tentados de implementarlo sin más.

No obstante, para aplicar éste método es necesario hacer algunas consideraciones:

Primera: el acceso a un elemento cualquiera de la lista debe tener un coste constante, es decir O(1). Si no es así, el coste del acceso al elemento debe tenerse en cuenta. Por ejemplo... El acceso mediante una lista enlazada a un elemento cualquiera suele tener un coste O(n). Eso significa que utilizar una búsqueda dicotómica nos cuesta O(n log₂n), que es bastante peor que el coste de una simple búsqueda secuencial (O(n)). Así que es necesario asegurarnos de esto. Sólo los arrays, y algunas ingeniosas implementaciones de lista pueden proporcionarnos un coste constante (o casi) de acceso a cualquier elemento. También lo podemos obtener en memoria secundaria con ficheros binarios de acceso aleatorio en los que todos sus registros tengan el mismo tamaño.

Segunda: Si se han de realizar varias búsquedas y la lista es susceptible de cambiar frecuentemente (porque insertemos o eliminemos elementos) debemos tener en cuenta que la lista debe mantenerse permanentemente en orden. Eso implica que las inserciones y los borrados deben mantener el orden, con lo cual, su complejidad no va a ser constante: probablemente estemos sacrificando la eficiencia de inserciones y borrados en pro de las búsquedas. Tenemos que asegurarnos de que nos compense.

Tercera: Por supuesto, resultaría absurdo realizar una ordenación de la lista antes de cada búsqueda. Incluso los algoritmos más eficientes de ordenación tienen un coste bastante elevado, que habría que añadir al de la propia búsqueda.

Cuarta: El hecho de que la lista esté ordenada antes de realizar la búsqueda es obligatorio. Si se aplica una búsqueda dicotómica a una lista no ordenada (aunque sólo fuera un elemento) se podría producir GIGO. Por supuesto, no se puede comprobar algorítmicamente esta condición, ya que el coste de la comprobación debería añadirse al de la búsqueda, haciendo que perdiera sus buenas propiedades.

¡¡¡Cuantas cosas!!! Entonces ¿Cuándo es de utilidad la búsqueda dicotómica? Pues prácticamente, solo en una situación: Cuando tengamos una lista de valores susceptibles de ser ordenados, y que la importancia que le demos a las operaciones de inserción o borrado de elementos sean muy muy muy muy inferior a la de las búsquedas.

La elaboración del algoritmo en sí es bastante secilla y se pueden hacer bastantes variantes (con mínimas diferencias entre ellas). Aquí tienes un pseudocódigo que lo describe y un ejemplo en C#. Si el algoritmo encuentra el valor, devolverá su posición en el array, y si no lo encuentra, devolverá un -1 (dado que las posiciones son positivas)

funcion busquedaBinaria(
        v:array[1..n] de enteros,
        b:entero
        ):entero
variables: inferior, superior, medio:entero
    resultado:entero;
empieza
//empezamos suponiendo que no hemos
//encontrado el valor
resultado=-1;
//el primer elemento que consideramos
inferior=1;
//el ultimo elemento que consideramos
superior=n;
mientras(resultado<0 y inferior<=superior)
   //calculamos la posición del elemento medio
   //entre inferior y superior
   medio=(inferior+superior)/2; //division entera
   si v[medio]=x //si lo hemos encontrado en medio
      resultado=medio
   si no 
      si b<v[medio] //esta en la mitad inferior
         superior=medio-1
      si no //esta en la mitad superior
         inferior=medio+1 
      fin si
   fin si
fin mientras
devolver resultado
terminar
 

int busquedaDicotomica(int[] v, int b)
{
   int inferior = 0;
   int superior = v.Length - 1;
   int medio;
   int resultado = -1;
   while (resultado<0 && inferior<=superior)
   {
      medio=(inferior+superior)/2;
      if (v[medio]==b) 
      {
         resultado=medio;
      }
      else
      {
         if (b<v[medio])
            superior=medio-1;
         else
            inferior=medio+1;
      }
   }
   return resultado;
}
 

wikipedia

paper

via Google