Universidad de Guadalajara Centro Universitario de los Altos CUALTOS Lic. En Ingeniería computacional

Búsqueda dicotómica o binaria

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,

Universidad de Guadalajara Centro Universitario de los Altos CUALTOS Lic. En Ingeniería computacional

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

Universidad de Guadalajara Centro Universitario de los Altos CUALTOS Lic. En Ingeniería computacional

busco no esté en el vector) realizo log2n 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 log2n), 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)

Universidad de Guadalajara Centro Universitario de los Altos CUALTOS Lic. En Ingeniería computacional

1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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

Quizá te estés preguntando si en lugar de hacer una búsqueda "dicotómica" la hacemos

"tricotómica" o "cuatricotómica" (es decir, dividir el intervalo de búsqueda en más trozos)

saldríamos ganando algo... pues realmente no: el resultado sería igual o peor. Puedes hacer

la prueba intuitivamente contando el número de comparaciones que harías en el peor caso.

Ten en cuenta que si dividimos el intervalo en tres en lugar de en dos, en el peor caso son

necesarias dos comparaciones por iteración, en lugar de una.... En la búsqueda dicotómica,

con dos comparaciones (en dos iteraciones) dividimos el intervalo en cuatro. Si hicieramos

la búsqueda "tricotómica", para dividir el intervalo en tres considerando un caso

promedio en unas ocasiones necesitamos una comparación y en otras dos. En un caso

promedio nos quedamos más o menos igual, pero con un algoritmo más complicado.