Algoritmos: Búsqueda dicotómica

Stoimen's Web Log desde hace un tiempo publica cada semana un post sobre Algoritmos. Habiendo llevado el curso de Algoritmos y Estructuras de Datos en la universidad -y habiéndolo aprobado con una nota decorosa- pensé en seguir los posts como una manera de refrescar mis algo oxidados conocimientos de algoritmia.


Ya van cinco algoritmos publicados y no he visto ninguno en la Universidad, así que parece que el profesor nos engañó al hacernos creer que sabíamos algoritmos. Me he propuesto remediar ese error, y he comenzado a leer Data Structures and Algorithms in Java para aprender lo que debí haber aprendido en la universidad. Esta serie de posts son una recopilación de conceptos producto de mi lectura.


Dicho esto, comenzamos:

¿Cómo localizarías un elemento en un arreglo ordenado? Una aproximación ingenua sería recorrer el arreglo desde la posición inicial (En Java, el índice 0) e ir recorriendo el arreglo elemento por elemento hasta localizar el elemento que estábamos buscando. Si asumimos el peor escenario posible -es decir, el elemento que buscábamos se encuentra al final del arreglo- este tipo de búsqueda requeriría N "pasos" par un arreglo de longitud N.

El enfoque anterior podría funcionar también para un arreglo desordenado, pero tratándose de un arreglo ordenado es ineficiente dado que no aprovechamos el hecho de tener el arreglo ordenado para reducir el número de pasos que le toma al algoritmo encontrar el elemento buscado. La búsqueda dicotómica nos permite aprovechar este atributo de nuestro arreglo para que -en el peor de los casos- la búsqueda tome sólamente lb (N) pasos (esto es el logaritmo en base 2 de N). Pongamos el algoritmo a prueba buscando un número X en un arreglo A de longitud 100 (N=100):

1. Tomemos el elemento que se encuentra exactamente al medio del arreglo (A[50]) y verificamos si es el elemento que buscábamos. 
2. Imaginemos que no lo es y que X es mayor que A[50]. Cómo se trata de un arreglo ordenado, ahora podemos afirmar con seguridad que X no se encuentre en A[49] ni en ninguno de los elementos que le preceden, por lo que sólo deberíamos buscar en los elementos entre A[51] y A[100]
3. Tenemos ahora un nuevo arreglo en el que buscar, y según nuestro algoritmo debemos verificar si el elemento ubicado en la mitad del arreglo -o sea A[75] -es el elemento que buscábamos.
4. Volvamos a pretender que no lo es,  pero que ahora X es menor que A[75]. Como este arreglo también se encuentra ordenado, concluimos que todos los elementos desde A[76] hasta A[100] son mayores que X, por lo que sólo deberíamos buscar entre A[51] hasta A[74]
5. Y así hasta que encontremos el número que buscábamos. 

Si tanta palabrería la pasamos a Java, obtenemos algo como esto:

      public int find(long searchKey) {  
           int lowerBound = 0;  
           int upperBound = nElems - 1;  
           int curIn;  
           while (true) {  
                curIn = (lowerBound + upperBound) / 2;  
                if (a[curIn] == searchKey) {  
                     return curIn;  
                } else if (lowerBound > upperBound) {  
                     return nElems;  
                } else {  
                     if (a[curIn] < searchKey) {  
                          lowerBound = curIn + 1;  
                     } else {  
                          upperBound = curIn - 1;  
                     }  
                }  
           }  
      }  

Ese método pertenece a una clase donde a[] es un atributo que representa el arreglo ordenado sobre el que buscamos y nElems es un atributo que contiene la longitud del arreglo. El método devuelve la posición en a[] en la que se encuentra searchKey, y en caso no la encuentre devuelve nElems que es la longitud del arreglo. La variable curIn representa el índice del elemento que se encuentra en el medio del arreglo que estamos evaluando, siendo lowerBound el índice del menor elemento del arreglo y upperBound  el índice del mayor elemento del arreglo. En cada iteración del bucle while se compara si a[curIn] es mayor o menor que el elemento buscado searchKey y en base al resultado de esta comparación se recalculan los valores de  upperBound  y lowerBound. Con dibujitos, sería algo así:

El número de "pasos" que necesasitamos para encontrar un elemento en un arreglo de longitud N viene a estar dado por la cantidad de veces que podemos dividir N sobre 2 (antes que el producto de esta división sea menor que 1). Este número en matemáticas es igual a lb(N), que es considerablemente menor que N de nuestro enfoque ingenuo del primer párrafo: si buscamos secuencialmente un arreglo de 100 elementos nos tomaría 100 pasos, mientras que si usamos la búsqueda dicotómica nos tomaría sólo 7 (aproximadamente el valor de lb(100)).

Código fuente e imágenes tomadas de Data Structures and Algorithms in Java.