En programación no son pocas la ocasiones en las que podemos necesitar que en un momento dado, nuestro programa realice la búsqueda de un elemento dentro de una lista ordenada (piénsese en una aplicación web en la que el nombre de usuario introducido he de buscarse en una base de datos). Este es un proceso que, para el caso de listas de pocos elementos, puede efectuarse con una simple búsqueda lineal (recorriendo la lista elemento a elemento). el problema surge cuando debemos hacer dicha búsqueda en listas extensas (de centenares, miles..de elementos) en el que dicho método de búsqueda se revela ineficiente, al hacer más lento (y con un mayor consumo de recursos) la ejecución de nuestro programa. Siendo en estos casos, más adecuados otros procedimientos como la «búsqueda binaria» del que hoy vamos a hablar e implementar en Python.
QUE ÉS Y COMO FUNCIONA:
También llamada «búsqueda de intervalo medio» o «búsqueda logarítmica«, la «búsqueda binaria« es un algoritmo que se emplea para localizar un elemento dentro de una lista o array, ordenada en el que se empieza tomando el valor del punto medio de la misma, comparándolo con el valor buscado, de modo que si ambos no coinciden se determina en cual de las dos mitades puede encontrarse el valor, desechándose aquella en la que no puede estar y repitiendo el proceso con la otra, hasta dar con dicho valor o concluir que este no se encuentra en la lista.
Veamos un sencillo ejemplo, para ilustrarlo mejor, en el que nos proponemos buscar un valor (en este caso, el 6) dentro de una lista de 7 valores numéricos ordenados de menor a mayor, cuyas posiciones se cuentan de 0 a 6:
Para la búsqueda de dicho valor daremos, en este caso, tres pasos:
1- Realizamos la comparación entre el valor buscado (2) y el elemento que ocupa la posición central dentro de la lista (8). Viéndose que este es mayor que dicho elemento buscado, lo que significa (en una lista ordenada de menor a mayor) que dicho valor (de encontrarse en la lista) estará entre los valores posicionados a la izquierda del valor central.
2- Se repite el proceso anterior con los valores de la izquierda, tomándose su elemento central (ahora el 4) y repitiéndose la misma comparación viéndose que 2<4 con lo que este tendrá que estar, otra vez, a la izquierda del valor central.
3- Finalmente llegamos al punto en al que solo queda un valor, que es (viendo el resultado de la comparación) precisamente, el buscado (2=2) con lo que queda así verificada su existencia en la lista, e identificada su posición (0).
Es posible que más de uno piense que este caso concreto podría haberse resuelto de modo más rápido mediante una búsqueda lineal al darse la doble circunstancia de tratarse de una lista de pocos elementos y hallarse el valor buscado, en la primera posición de la lista (de hecho habría bastado con un solo paso. Sin embargo no hay que olvidar que se trata de un sencillo ejemplo para ilustrar el método que emplearemos cuando tengamos que trabajar con listas extensas, en donde el elemento a buscar podrá en cada ocasión estar en cualquier posición de la misma.
Nota: En este artículo nos centramos en la búsqueda de valores numéricos, no obstante hay que recordar que este procedimiento podría aplicarse a la búsqueda de palabras en una lista, pues lo valores de comparación valen igualmente para caracteres alfabéticos. Lo importante es que nuestra lista esté ordenada.
IMPLEMENTACIÓN EN PYTHON:
A continuación vamos a ver un sencillo ejemplo de implementación de este algoritmo, usando la sintaxis de Python. En esta ocasión vamos a trabajar con una lista de 20 valores (con posiciones de 0 a 19) en la que (a diferencia del caso anterior) vamos a contemplar el peor escenario posible, en el que el valor a buscar será precisamente el ubicado al final de la lista. De todos modos, empezaremos empleando la búsqueda lineal para luego compararla con la binaria:
Output:
Tenemos aquí una sencilla función que ha recorrido la lista proporcionada como argumento, comparando cada valor con el valor buscado (20). Imprimiéndose en la salida la posición en el que este ha sido encontrado (19) y el número de comparaciones (o pasos) que se han tenido que efectuar (20 pasos).
Pasemos ahora a realizar la misma búsqueda empleado la «búsqueda binaria» objeto de esta entrada:
Output:
En este caso estamos traduciendo el procedimiento de «búsqueda binaria» a código Python, aplicándolo al mismo caso anterior, obteniendo la misma posición, pero en este caso en tan solo 5 pasos (frente a los 20 del caso anterior) lo que supone un nada despreciable ahorro de pasos en la búsqueda, ahorro que será más significativo en aquellos casos en los que necesitemos trabajar con grandes cantidades de información, que requieran una mayor optimización de recursos.
Saludos.
El Programador Chapuzas 