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:
List<Product> shelf = List.of( new Product("3800200101112", "Harina"), new Product("3800200104403", "Azúcar"), new Product("3800200107251", "Aceite"), new Product("3800200102690", "Arroz"), new Product("3800200109958", "Sal"), new 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á»: -1, porque no existe el lugar -1.
Míralo
El puntero en el estante
static int find(List<Product> shelf, String barcode) { for (int i = 0; i < shelf.size(); i++) { if (shelf.get(i).barcode().equals(barcode)) { return i; } } return -1;}int rice = find(shelf, "3800200102690");System.out.println("3800200102690 -> " + rice + " " + shelf.get(rice).name());System.out.println("3800200100000 -> " + find(shelf, "3800200100000"));3800200102690 -> 3 Arroz3800200100000 -> -1static int find(List<Product> shelf, String barcode) { for (int i = 0; i < shelf.size(); i++) { if (shelf.get(i).barcode().equals(barcode)) { return i; } } return -1;}
int rice = find(shelf, "3800200102690");int 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 -1 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á.
Los códigos de barras se comparan con equals, no con ==. Con texto, == pregunta si es el mismo objeto en memoria, y el código que llega del escáner es otro objeto con los mismos dígitos.
Pruébalo
Completa
¿Qué devuelve find cuando se acaban las cajas?
static int find(List<Product> shelf, String barcode) {
for (int i = 0; i < shelf.size(); i++) {
if (shelf.get(i).barcode().equals(barcode)) {
return i;
}
}
return ;
}-1 no es un lugar de la lista, así que no se puede confundir con un producto encontrado. Quien llama a find comprueba -1 antes de usar el resultado.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:
static int comparisons(List<Product> shelf, String barcode) { int count = 0; for (Product product : shelf) { count++; if (product.barcode().equals(barcode)) { return count; } } return count;}System.out.println("Harina: " + comparisons(shelf, "3800200101112"));System.out.println("Arroz: " + comparisons(shelf, "3800200102690"));System.out.println("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?
static int comparisons(List<Product> shelf, String barcode) { int count = 0; for (Product product : shelf) { count++; if (product.barcode().equals(barcode)) { return count; } } return count;}
System.out.println("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:
List<String> barcodes = List.of( "3800200101112", "3800200104403", "3800200107251", "3800200102690", "3800200109958", "3800200105837");System.out.println(barcodes.indexOf("3800200102690"));System.out.println(barcodes.indexOf("3800200100000"));System.out.println(barcodes.contains("3800200102690"));3-1trueindexOf devuelve el lugar o -1, y contains solo «sí» o «no». Ambos comparan con equals desde el primer elemento: O(n). Para una lista de productos por código de barras, Java no tiene un método listo; escribes el bucle o usas un stream (IntStream.range(...).filter(...).findFirst()), que también va en orden.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á»:
static int find(List<Product> shelf, String barcode) { for (int i = 0; i < shelf.size(); i++) { if (shelf.get(i).barcode().equals(barcode)) { return i; } else { return -1; } } return -1;}System.out.println(find(shelf, "3800200101112"));System.out.println(find(shelf, "3800200102690"));0-1¿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 (
HashMap): 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.
Map<String, Product> byBarcode = new HashMap<>();for (Product product : shelf) { byBarcode.put(product.barcode(), product);}System.out.println(byBarcode.get("3800200102690").name());System.out.println(byBarcode.get("3800200100000"));ArroznullLa 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 findAll(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