30. Búsqueda binaria¶
El algoritmo de búsqueda binaria es más rápido que el algoritmo de búsqueda lineal estudiado en la unidad anterior.
Este algoritmo aprovecha que una lista ya está ordenada para encontrar el elemento buscado con mayor rapidez. Estos son los pasos del algoritmo:
- Repite todo mientras haya lista en la que buscar.
- Buscamos el elemento en la mitad de la lista.
- Si se encuentra el elemento, devuelve la posición del elemento encontrado.
- Si el elemento buscado es mayor que el elemento de la mitad de la lista, dividimos la lista en dos y solo buscaremos en la mitad superior de la lista.
- En caso de que el elemento buscado sea menor que el elemento de la mitad de la lista, dividimos la lista en dos y solo buscaremos en la mitad inferior de la lista.
- Si no se ha encontrado el elemento, devuelve
None
Ejemplo de búsqueda binaria¶
Este es un ejemplo de lista para buscar un elemento, con las posiciones de los números:
lista = [
8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ]
# ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Vamos a buscar el elemento 89 en esta lista con búsqueda binaria.
Primero buscamos en la mitad de la lista, posición 9, lo que nos devuelve el número 46. Como 46 es menor que 89, sabemos que el elemento buscado solo puede estar en la mitad superior de la lista:
lista = [
8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ]
# ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# 10 11 12 13 14 15 16 17 18 19
Ahora buscamos en la mitad de la parte superior de la lista, en la posición 14, lo que nos devuelve el número 75. Como 75 es menor que 87, sabemos que el elemento buscado solo pude estar en la mitad superior de la lista:
lista = [
8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ]
# ^ ^ ^ ^ ^
# 15 16 17 18 19
Volvemos a buscar en la mitad de la parte de la lista superior, en la posición 17, lo que nos devuelve el número 89. Este es el elemento buscado, por lo que podemos devolver la posición 17.
Como podemos comprobar, con solo 3 comparaciones se ha encontrado el elemento buscado en la posición 17. Una búsqueda lineal habría requerido 18 comparaciones en total.
La búsqueda binaria, por lo tanto, es mucho más rápida que la búsqueda lineal, sobre todo en listas muy grandes de elementos, con la desventaja de que necesita buscar en una lista que ya esté ordenada.
Programa de búsqueda binaria¶
El programa para realizar una búsqueda binaria tendrá dos índices,
inicio y final.
Uno apunta al comienzo de la lista y otro al final de la lista.
Estos índices se actualizarán a medida que conozcamos qué parte de
la lista puede contener al elemento buscado:
def busqueda_binaria(lista, buscado):
inicio = 0
final = len(lista) - 1
while inicio <= final:
medio = (inicio + final) // 2
if lista[medio] == buscado:
return medio
elif lista[medio] < buscado:
inicio = medio + 1
else:
final = medio - 1
return None
lista = [
8, 13, 17, 19, 33, 35, 40, 42, 44, 46,
51, 53, 63, 72, 75, 85, 87, 89, 92, 99
]
buscado = 87
resultado = busqueda_binaria(lista, buscado)
if resultado == None:
print(f'El elemento {buscado} no se encuentra en la lista')
else:
print(f'El elemento {buscado} se encuentra en la posición {resultado}')
Ejercicios¶
Programa una función de búsqueda binaria que devuelva la posición en la que se debería colocar un nuevo elemento para que quede ordenado dentro de una lista de números ya ordenados.
Pista:
def posicion_insertar(lista, nuevo_numero): inicio = 0 final = len(lista) - 1 while inicio <= final: ... ... ... return ... lista = [ 8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ] nuevo_numero = 68 posicion = posicion_insertar(lista, nuevo_numero) print(f'El número {nuevo_numero} debería insertarse en la posición {posicion}')
Salida:
El número 68 debería insertarse en la posición 13
Prueba el programa con los números 7, 25, 48 y 100.
Los resultados correctos son las posiciones 0, 4, 10 y 20.