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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#!/usr/bin/env python3 def lineal_search(list, key): """ Retorna la posición del valor en la lista en caso de ser encontrado y el número de intentos. """ tries = 0 for i, value in enumerate(list): tries += 1 if value == key: return tries, i return tries, -1 list = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"] tries, position = lineal_search(list, "h") if position != -1: print("Coincidencia en la posición: {}, en {} intentos".format(position, tries)) else: print("No se encontraron coincidencias.") |
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:
|
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 |
#!/usr/bin/env python3 def binary_search(list, key): """ Retorna la posición del valor en la lista en caso de ser encontrado y el número de intentos. La lista debe estar ordenada para qué funcione la búsqueda. """ tries = 0 left = 0 right = len(list) - 1 while left <= right: tries += 1 middle = (left + right) // 2 if list[middle] == key: return tries, middle if list[middle] > key: right = middle - 1 if list[middle] < key: left = middle + 1 return tries, -1 list = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"] tries, position = binary_search(list, "h") if position != -1: print("Coincidencia en la posición: {}, en {} intentos".format(position, tries)) else: print("No se encontraron coincidencias.") |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#!/usr/bin/env python3 from bisect import bisect_left def binary_search(list, key): tries = 0 i = bisect_left(list, key) if i != len(list) and list[i] == key: return tries, i else: return tries, -1 list = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"] tries, position = binary_search(list, "h") if position != -1: print("Coincidencia en la posición: {}, en {} intentos".format(position, tries)) else: print("No se encontraron coincidencias.") |
