Cómo funciona
Se mira cada número de izquierda a derecha y se compara con el buscado. Si coincide, la búsqueda
termina; si no, se descarta y se pasa al siguiente. Cada comparación descarta
un solo número.
No exige nada a los datos: funciona aunque estén desordenados, y también en listas enlazadas o en
datos que llegan de uno en uno. El precio es que, para estar seguro de que un valor no está,
hay que mirarlos todos.
Paso a paso: buscar 7 en [8, 3, 5, 7, 2]
- 01i = 0, 1, 2: 8, 3 y 5 no son el 7. Se descartan de uno en uno.
- 02i = 3: A[3] = 7. Encontrado en la posición 3 tras 4 comparaciones.
- 03Buscando el 6: ninguno coincide. Hacen falta 5 comparaciones, una por número, para poder decir que no está: el peor caso.
¿Y si los datos estuvieran ordenados?
Entonces cada comparación podría descartar media tabla: es la búsqueda binaria. Con un millón de números,
la búsqueda lineal puede necesitar un millón de comparaciones y la binaria, como mucho 20. Pero ordenar
cuesta más que una búsqueda lineal, así que solo compensa si se va a buscar muchas veces.
Complejidad
- Mejor caso
- O(1)
- Caso promedio
- O(n)
- Peor caso
- O(n)
- Espacio extra
- O(1)
- Requisito
- Ninguno
- Datos
- Cualquier orden