30. Cerca binària¶
L’algoritme de cerca binària és més ràpid que l’algoritme de cerca lineal estudiat a la unitat anterior.
Aquest algoritme aprofita que una llista ja està ordenada per trobar l’element buscat més ràpidament. Aquests són els passos de l'algorisme:
- Repetiu -ho tot mentre estigui a punt per cercar.
- Busquem l’element al mig de la llista.
- Si es troba l’element, retorna la posició de l’element que es troba.
- Si l’element buscat és ** major ** que l’element mig de la llista, dividim la llista en dos i només buscarem a la meitat superior de la llista.
- En cas que l’element buscat sigui ** més petit ** que l’element mig de la llista, dividim la llista en dos i només buscarem a la meitat inferior de la llista.
- Si no s'ha trobat l'element, retorna `` cap ''`
Exemple de cerca binària¶
Aquest és un exemple de llista per trobar un element, amb les posicions dels 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
Anem a buscar l’element 89 d’aquesta llista amb la cerca binària.
Primer mirem al mig de la llista, la posició 9, que retorna el número 46. Com a 46 és inferior a 89, sabem que l’element buscat només pot estar a la meitat superior de la llista
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
Ara mirem a la meitat de la part superior de la llista, a la posició 14, que retorna el número 75. Com a 75 és inferior a 87, sabem que l’element buscat només podria estar a la meitat superior de la llista
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
Mirem enrere al mig de la llista superior, a la posició 17, que retorna el número 89. Aquest és l’element buscat, de manera que podem tornar la posició 17.
Com podem verificar, amb només 3 comparacions s'ha trobat l'element cercat a la posició 17. Una cerca lineal hauria requerit 18 comparacions en total.
La cerca binària, per tant, és molt més ràpida que la cerca lineal, sobretot en llistes d’elements molt grans, amb l’inconvenient que heu de cercar en una llista que ja està ordenada.
Programa de cerca binària¶
El programa per dur a terme una cerca binària tindrà dos índexs, `` Home '' i `` Final``. Un apunta al començament de la llista i un altre al final de la llista. Aquests índexs s’actualitzaran ja que sabem quina part de la llista pot contenir l’element buscat
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}')
Exercicis¶
Programa una funció de cerca binària que retorna la posició en què s’ha de col·locar un nou element de manera que s’ordeni dins d’una llista de números ja ordenats.
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}')
Sortida
El número 68 debería insertarse en la posición 13
Proveu el programa amb els números 7, 25, 48 i 100.
Els resultats correctes són les posicions 0, 4, 10 i 20.