Búsqueda lineal
En resumen: La búsqueda lineal revisa los elementos uno por uno hasta encontrar el buscado o llegar al final: O(n) comparaciones, y funciona con una lista sin ordenar.
Problema
El escáner del almacén
En el almacén los productos están anotados en una lista en el orden en que llegaron: la harina del lunes, el azúcar del martes, el aceite, el arroz. Un trabajador escanea una caja y el programa debe encontrar el producto por su código de barras:
shelf = [ Product("3800200101112", "Harina"), Product("3800200104403", "Azúcar"), Product("3800200107251", "Aceite"), Product("3800200102690", "Arroz"), Product("3800200109958", "Sal"), Product("3800200105837", "Café"),]Los códigos de barras no están ordenados. No puedes abrir la lista por la mitad y decir «el arroz está más adelante»: el siguiente código puede ser cualquiera. ¿Cómo encuentras el producto y cuánto cuesta cuando hay 50 000 productos y 2000 escaneos al día?
La idea
Miras cada caja
Como el orden no ayuda, solo queda una cosa: empiezas por la primera caja y comparas su código de barras con el que buscas. Si coincide, terminaste: devuelves el lugar. Si no, pasas a la siguiente. Si las cajas se acaban, el producto no está.
Esta es la búsqueda lineal: recorres los elementos uno por uno hasta encontrar el que buscas o llegar al final. Devuelve el lugar (el índice) o una señal de «no está»: None.
Míralo
El puntero en el estante
def find(shelf, barcode): for i, product in enumerate(shelf): if product.barcode == barcode: return i return Nonerice = find(shelf, "3800200102690")print("3800200102690 ->", rice, shelf[rice].name)print("3800200100000 ->", find(shelf, "3800200100000"))3800200102690 -> 3 Arroz3800200100000 -> Nonedef find(shelf, barcode): for i, product in enumerate(shelf): if product.barcode == barcode: return i return None
rice = find(shelf, "3800200102690")missing = find(shelf, "3800200100000")Paso a paso, en palabras
- El escáner lee el código de barras del arroz: 3800200102690. find empieza por la primera caja.
- Compara el código de barras de cada caja con el buscado: harina, azúcar, aceite. No coincide.
- La cuarta caja es el arroz. return 3: encontrado tras 4 comparaciones.
- Un código de barras que el almacén no tiene: 3800200100000. find empieza otra vez desde el principio.
- El puntero pasa por todas las cajas y ninguna coincide.
- Se acaban las cajas: return None tras 6 comparaciones. Un producto que falta es el peor caso: n comparaciones con n cajas.
El arroz se encuentra tras 4 comparaciones. El código que falta pasa por las 6 cajas: es la única manera de decir que no está.
En Python -1 es un índice real: shelf[-1] es el último producto. Si find devolviera -1, un código como shelf[find(shelf, code)].name daría el café para un código de barras que no existe, sin ningún error. Por eso «no está» es None, y shelf[None] se detiene al instante con un TypeError.
Pruébalo
Completa
¿Qué devuelve find cuando se acaban las cajas?
def find(shelf, barcode):
for i, product in enumerate(shelf):
if product.barcode == barcode:
return i
return None significa «sin valor». -1 es un índice real en Python (el último elemento), así que no sirve para «no está».La idea
Cuántas comparaciones
El número de comparaciones depende de dónde está el producto:
- el mejor caso: la primera caja, 1 comparación;
- el peor caso: la última caja o un producto que no está, n comparaciones;
- el caso habitual: si cada lugar es igual de probable, en promedio unas n/2.
El peor caso y el habitual crecen con n, así que la búsqueda lineal es O(n). El programa cuenta:
def comparisons(shelf, barcode): count = 0 for product in shelf: count += 1 if product.barcode == barcode: return count return countprint("Harina:", comparisons(shelf, "3800200101112"))print("Arroz:", comparisons(shelf, "3800200102690"))print("Falta:", comparisons(shelf, "3800200100000"))Harina: 1Arroz: 4Falta: 6Ejecuta los dos casos extremos en un almacén grande. Contamos una comparación por caja:
- El código de barras no está (peor caso)
O(n) - El primer producto (mejor caso)
O(1)
| Algoritmo | n = 10 | n = 1000 | n = 100.000 |
|---|---|---|---|
| El código de barras no está (peor caso) | 10 | 1000 | 100.000 |
| El primer producto (mejor caso) | 1 | 1 | 1 |
La primera caja cuesta 1 comparación para cualquier n: O(1). Un producto que falta cuesta n: con 100 000 productos son 100 000 comparaciones. La memoria es O(1): un índice.
Pruébalo
Predice la salida
La sal es la quinta caja del estante. ¿Cuántas comparaciones hace la búsqueda?
def comparisons(shelf, barcode): count = 0 for product in shelf: count += 1 if product.barcode == barcode: return count return count
print("Sal:", comparisons(shelf, "3800200109958"))Míralo
Las funciones incorporadas buscan igual
Cada lenguaje tiene una búsqueda lista en una lista. Por dentro es el mismo bucle:
barcodes = [ "3800200101112", "3800200104403", "3800200107251", "3800200102690", "3800200109958", "3800200105837",]print(barcodes.index("3800200102690"))print("3800200100000" in barcodes)try: barcodes.index("3800200100000")except ValueError as e: print("ValueError:", e)3FalseValueError: '3800200100000' is not in listindex devuelve el lugar y, si no está, lanza ValueError. in da solo True o False. Ambos van desde el primer elemento: O(n). Así que if code in barcodes: barcodes.index(code) busca dos veces.Una llamada parece una sola operación, pero por dentro hay hasta n comparaciones. La función incorporada es más rápida que tu bucle por un factor constante, no por un orden de magnitud.
Pruébalo
Encuentra el error
Un compañero escribió la búsqueda así. La harina se encuentra, y el arroz «no está»:
def find(shelf, barcode): for i, product in enumerate(shelf): if product.barcode == barcode: return i else: return None return Noneprint(find(shelf, "3800200101112"))print(find(shelf, "3800200102690"))0None¿En qué línea está el error?
Elige la línea con el error.
Un else con un return dentro del bucle devuelve «no está» justo después de la primera caja que no coincide. El bucle nunca llega a la segunda. La prueba con la harina pasa, porque está la primera. «No está» solo se puede decir cuando las cajas se acaban: quita el else y deja un único «no está» después del bucle.
La idea
Cuándo conviene y cuándo no
La búsqueda lineal es la elección correcta cuando:
- hay pocos productos: diez o cien comparaciones no se notan;
- buscas una sola vez: cualquier forma más rápida necesita antes al menos n pasos de preparación;
- los datos están sin ordenar o cambian todo el tiempo, y no hay nada que mantener.
No lo es cuando hay muchas búsquedas. 2000 escaneos al día entre 50 000 productos son hasta 100 000 000 de comparaciones. Entonces preparas los datos una vez:
- una tabla código de barras → producto (
dict): 50 000 pasos una vez, y después cada búsqueda es O(1) en promedio; - una lista ordenada y la búsqueda binaria: ordenar es O(n log n) una vez, y cada búsqueda posterior es O(log n), unas 16 comparaciones para 50 000.
by_barcode = {product.barcode: product for product in shelf}print(by_barcode["3800200102690"].name)print(by_barcode.get("3800200100000"))ArrozNoneLa tabla cuesta memoria: otros n lugares. Es el mismo intercambio de tiempo por memoria que el conjunto de la lección «Complejidad en espacio».
Ejercicio
Todas las cajas de un producto
Resuelve la tarea en tu editor.
Inventario. Un producto puede haber llegado en varias entregas y estar en varios lugares de la lista. Escribe find_all(shelf, barcode), que devuelva todos los lugares del código de barras, no solo el primero. El estante es como el de arriba, con más arroz y más sal al final (lugares 6 y 7).
Arroz: 3, 6Sal: 4, 7Más tareas
- El último lugar. Devuelve el último lugar del código de barras. ¿Por dónde conviene empezar?
- Por nombre, sin distinguir mayúsculas. Encuentra el producto por nombre («arroz» y «Arroz» son lo mismo). ¿Cuántas comparaciones hay en el peor caso?
- Productos bajo el mínimo. Lista todos los productos con menos de 10 unidades en existencias. ¿Puedes parar antes del final?
Test