Durante el corto tiempo que tuve cuenta en CuriousCat (lo borré porque para recibir insultos anónimos ya me llega con Tweeter y los comentarios de este blog) alguien me pidió que escribiera sobre la diferencia entre una búsqueda binaria y una búsqueda dicotómica. Eso se lo contesté rápidamente allí: búsqueda dicotómica y búsqueda binaria son sinónimos, no hay diferencia.
¿En qué consiste la búsqueda binaria?
Cuando hablamos de búsqueda binaria hablamos de un algoritmo, una serie de instrucciones para que un programa informático realice una tarea. Concretamente de un algoritmo de búsqueda, es decir, la serie de instrucciones necesarias para encontrar un valor dentro de una colección de valores. La búsqueda binaria está pensada para buscar un elemento dentro de una colección ordenada. Vamos a explicar cómo funciona con un ejemplo: imagínate que tuvieras una lista con todos los habitantes de Barcelona ordenada por la primera letra de su apellido, tienes que buscar a alguien que se apellida «Martínez» ¿te pondrías a mirar la lista desde el principio hasta llegar a ese nombre? Son millones de comprobaciones. Ese procedimiento sería el de una búsqueda lineal: comprobar todos los valores hasta encontrar el deseado, funciona pero es muy lento, tiene utilidad cuando no queda más remedio (una colección desordenada) pero es demasiado ineficiente para una lista ordenada.
Aplicando una búsqueda binaria a ese ejemplo lo que haríamos sería encontrar primero el valor del medio de la lista, dividir la lista en dos mitades y comprobar si el valor intermedio es el que buscamos, es menor o es mayor. Si se diera la casualidad de que es el que buscamos la búsqueda ya estaría finalizada, si el valor intermedio es menor descartaríamos la mitad inferior de la lista y si es mayor descartaríamos la mitad superior. Ahora que localizamos en qué mitad tiene que estar nuestro valor repetimos el procedimiento sobre esa mitad, creando otras dos mitades y de nuevo repitiendo el procedimiento hasta dar con nuestro valor. En cada iteración descartamos la mitad de los datos que teníamos, lo que reduce el tiempo de búsqueda respecto a la lineal.
¿Se usa este algoritmo?
La mayoría de lenguajes de programación o frameworks ya tienen funciones de búsquea integradas muy bien optimizadas, así que no es habitual que alguien tenga que escribir una función de búsquea binaria, excepto en ejercicios académicos para aprender algoritmia. Yo personalmente he utilizado este método para buscar entre conjuntos de datos manualmente, cuando no disponía de un índice. Aquí abajo os dejo una implementación del algoritmo en Javascript:
function buscaDicotomica(valor, conjunto) {
//valor es lo que vamos a buscar, cojunto es el array donde lo buscamos
var ini = 0; //inicio del array
var fin = conjunto.length - 1; //fin del array
var pos = -1;
var finaliza = false;
var media;
while (finaliza === false && ini<= fin) {
media= Math.floor((ini+ fin)/2);
if (conjunto[media] == valor) {
finaliza = true;
pos = media;
} else if (conjunto[media] > valor) { //si está en la mitad inferior
fin= media - 1;
} else { //si está en la mitad superior
ini= media+ 1;
}
}
return pos;
}
DonnierocK 