La reserva 1085, mientras el cliente espera
Trabajas en la recepción de un hotel de Málaga. Un cliente da su número de reserva: 1085.
El sistema guarda miles de reservas. Podría mirarlas una a una desde la primera.
Pero las reservas están ordenadas por número. Con ese orden hay un método mucho más rápido. En esta lección ves los dos y cuándo usar cada uno.
Al final de esta lección
Nota
Puedo encontrar un elemento con la búsqueda lineal y con la búsqueda binaria.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Algoritmo | una serie de pasos que resuelve un problema |
| Búsqueda lineal | mirar los elementos uno a uno, en orden |
| Ordenada | colocada de menor a mayor |
| Búsqueda binaria | mirar el centro y descartar una mitad |
| Paso | una comparación con un elemento |
| -1 | la respuesta acordada para «no está» |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La búsqueda lineal mira uno a uno
La búsqueda lineal empieza por el primer elemento. Lo compara con lo que buscas y pasa al siguiente.
Para cuando lo encuentra o cuando se acaba la lista. Funciona con cualquier lista, ordenada o no.
En el peor caso mira todos los elementos. Con 5000 matrículas, pueden ser 5000 pasos.
Prueba: buscar una furgoneta
# Matrículas de las furgonetas de reparto, sin ningún orden.
vans = ["4821 KLM", "1093 JBD", "7710 LPS", "2254 HGT", "6638 MCR"]
target = "2254 HGT"
steps = 0
found_at = -1
for i in range(len(vans)):
steps = steps + 1
if vans[i] == target:
found_at = i
break # ya la tenemos: no hace falta mirar más
print("Posición:", found_at, "| pasos:", steps)
# Busca "9999 ZZZ", que no está, y cuenta los pasos.
La búsqueda binaria parte la lista en dos
La búsqueda binaria solo sirve si la lista está ordenada. Empieza mirando el elemento del centro.
Si es el que buscas, termina. Si buscas un número mayor, descarta toda la mitad izquierda. Si buscas uno menor, descarta la mitad derecha.
Después repite con lo que queda. En cada paso, la lista se reduce a la mitad.
Prueba: buscar una reserva
# Números de reserva de un hotel de Málaga, ordenados de menor a mayor.
bookings = [1004, 1017, 1023, 1038, 1046, 1052, 1061, 1079, 1085, 1093, 1108]
target = 1085
low = 0
high = len(bookings) - 1
steps = 0
while low <= high:
steps = steps + 1
middle = (low + high) // 2
print("Paso", steps, "| miro el índice", middle, "=", bookings[middle])
if bookings[middle] == target:
print("Encontrada en el índice", middle)
break
elif bookings[middle] < target:
low = middle + 1 # la reserva está a la derecha
else:
high = middle - 1 # la reserva está a la izquierda
# Busca 1004 y después 1108. ¿Cuántos pasos hacen falta?
Ejemplo resuelto: buscar 1085 entre 11 reservas
| Paso | low | high | middle | Valor en el centro | Decisión |
|---|---|---|---|---|---|
| 1 | 0 | 10 | 5 | 1052 | 1085 es mayor: a la derecha |
| 2 | 6 | 10 | 8 | 1085 | Encontrada |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un error frecuente
Advertencia
Mucha gente cree que la búsqueda binaria funciona con cualquier lista. No es así. Si la lista no está ordenada, al descartar una mitad puedes descartar justo el elemento buscado. El programa dice entonces que no está, aunque sí está.
Ejemplo resuelto: pasos en el peor caso
| Elementos | Lineal, como mucho | Binaria, como mucho |
|---|---|---|
| 11 | 11 pasos | 4 pasos |
| 1000 | 1000 pasos | 10 pasos |
| 1 000 000 | 1 000 000 pasos | 20 pasos |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.