Buscar un número de pedido
La búsqueda lineal y la búsqueda binaria son dos formas de encontrar un dato en una lista. La binaria es mucho más rápida, pero solo funciona si la lista está ordenada.
Una tienda tiene un millón de números de pedido. Mirarlos uno a uno puede costar un millón de pasos. Con la búsqueda binaria bastan 20.
Al final de esta lección
Nota
Puedo comparar la búsqueda lineal con la búsqueda binaria y decir cuándo usar cada una.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Búsqueda lineal | mirar los elementos de uno en uno hasta dar con el dato | |
| Búsqueda binaria | mirar el elemento del medio y descartar la mitad | |
| Lista ordenada | una lista de menor a mayor | |
| Posición | el número del lugar que ocupa un elemento; empieza en 0 | 0 |
| Mitad | la parte de la lista que aún puede tener el dato |
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 y sigue hasta encontrar el dato o llegar al final. No necesita que la lista esté ordenada.
En el mejor caso el dato es el primero: un paso. En el peor, es el último o no está: n pasos.
Una búsqueda lineal con sus pasos
# Búsqueda lineal: mira los pedidos de uno en uno.
orders = [3, 8, 15, 21, 34, 40, 52, 67, 71, 90, 95]
target = 67
steps = 0
found = -1
for i in range(len(orders)):
steps = steps + 1
if orders[i] == target:
found = i
break
print("Posición:", found, "Pasos:", steps)
# Cambia target a 3 y luego a 50.
grep también busca línea a línea
seq 1 1000 | grep -n -x 777Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
La búsqueda binaria descarta la mitad
Si la lista está ordenada, mira el elemento del medio. Si es menor que el dato, el dato está a la derecha y descartas la mitad izquierda. Si es mayor, descartas la derecha.
Repites con la mitad que queda. Cada paso parte la lista por la mitad.
Buscar el 67 paso a paso
| Paso | Límites | Medio | Qué pasa |
|---|---|---|---|
| 1 | 0 a 10 | posición 5, vale 40 | 40 es menor: se descarta la izquierda |
| 2 | 6 a 10 | posición 8, vale 71 | 71 es mayor: se descarta la derecha |
| 3 | 6 a 7 | posición 6, vale 52 | 52 es menor: se descarta la izquierda |
| 4 | 7 a 7 | posición 7, vale 67 | Encontrado |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La misma búsqueda, binaria
# Búsqueda binaria: mira siempre el elemento del medio.
orders = [3, 8, 15, 21, 34, 40, 52, 67, 71, 90, 95]
target = 67
low = 0
high = len(orders) - 1
steps = 0
found = -1
while low <= high and found == -1:
middle = (low + high) // 2
steps = steps + 1
if orders[middle] == target:
found = middle
elif orders[middle] < target:
low = middle + 1
else:
high = middle - 1
print("Posición:", found, "Pasos:", steps)
# Cambia target a 3 y luego a 50.
Un error frecuente
Advertencia
Mucha gente cree que la búsqueda binaria sirve con cualquier lista. No: solo funciona si la lista está ordenada. Sin orden, descartar una mitad puede tirar el dato. Si la lista no está ordenada, usa la búsqueda lineal.
Cuántos pasos necesita cada búsqueda
En el peor caso, la lineal da n pasos. La binaria da unos log2 de n pasos: las veces que puedes partir n por la mitad, más uno.
Con 1.000 datos son 1.000 pasos contra 10. Con un millón son un millón contra 20. El siguiente Run calcula esos 20.
Pasos de la binaria con un millón
python3 -c "import math; print(math.floor(math.log2(1000000)) + 1)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Peor caso según n
| n | Lineal | Binaria |
|---|---|---|
| 10 | 10 | 4 |
| 1.000 | 1.000 | 10 |
| 1.000.000 | 1.000.000 | 20 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.