Cómo funcionan las Búsquedas Lineales y Binarias en Python. El módulo Bisect.

En este breve Tutorial, te explico las diferencias entre una Búsqueda Lineal y una Búsqueda Binaria y cuales son las ventajas de usar cada una de ellas. Para ello usaremos programación en Python y opcionalmente el módulo Bisect.

¿Qué es una Búsqueda Lineal?

Una Búsqueda Lineal es aquella que revisa elemento a elemento, hasta que da con el resultado correcto. Por lo que cuantos más elementos contiene una lista, más tiempo tardará nuestro proceso en encontrar un resultado válido.

Si nuestra lista contiene 1.000 elementos, podríamos necesitar hasta 1.000 comparaciones hasta dar con el resultado correcto, si es que el valor está al final de la lista o ni siquiera está presente en ella.

Veamos un ejemplo escrito en Python, de cómo funciona una búsqueda lineal:

En este caso, hemos necesitado recorrer la lista 8 veces hasta dar con el elemento que estamos buscando.

¿Qué es una Búsqueda Binaria?

Una Búsqueda Binaria es un algoritmo de búsqueda que se encarga de encontrar un valor en un array de datos, siempre que sus datos estén ordenados. Cuanto mayor sea el array o la lista de datos, más eficiente será nuestra búsqueda.

Por ejemplo, para una lista con 10.000 elementos, una Búsqueda Binaria tan sólo necesita realizar 17 comparaciones, hasta dar con el resultado correcto.

Primero se compara el dato que estamos buscando, con el dato situado en la mitad de la lista y comprobamos si este es mayor o menor. Si es menor, ya sabemos que está situado al principio de la lista y si es mayor, lo estará al final de ella.

De esta forma, con tan sólo una comparación, hemos eliminado la mitad de posibles resultados a comprobar. El proceso se repite una y otra vez hasta encontrar el elemento correcto. Veamos como funciona una búsqueda Binaria aplicada al ejemplo anterior:

Para este caso tan sólo hemos necesitado 4 intentos hasta dar con valor correcto. Este sólo es un ejemplo y no tendría sentido realizar una búsqueda binaria en una lista con tan pocos elementos.

Recuerda que para que una búsqueda binaria funcione, debe estar ordenada, por lo que en caso de no estarlo, debemos ordenarla. Ordenar una lista enorme de datos ralentizará nuestro proceso y tan sólo tendrá sentido si vamos a realizar varias búsquedas. En caso contrario será mejor usar una búsqueda lineal, que es más simple y rápida de ejecutar.

Aplicar búsquedas binarias cuando tratamos de solucionar problemas, sólo será buena idea cuando tratamos de probar una gran lista de posibles resultados. Las listas pueden contener lo que deseemos, desde líneas de código, nombres de ficheros, extensiones, etc …

El módulo Bisect de Python

El módulo Bisect de Python nos ayuda a simplificar nuestro código y nos permite buscar hacia la derecha o hacia la izquierda. Tan sólo necesitamos pasarle una lista de valores y el valor que estamos buscando.

 

Deja una respuesta

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.