Búsqueda lineal
La búsqueda lineal es lo que haces cuando buscas un nombre en una lista sin ordenar: empiezas por arriba y lees hacia abajo hasta encontrarlo. Es la búsqueda más sencilla que existe, funciona con cualquier lista y, para listas cortas, a menudo es todo lo que necesitas.
La idea
Compara el valor buscado con el primer valor de la lista. Si son iguales, para: el valor buscado está en la posición 1. Si no, compáralo con el segundo valor, luego con el tercero, y así sucesivamente. Si el último valor tampoco coincide, el valor buscado no está en la lista. No hace falta saber nada de la lista de antemano: no tiene que estar ordenada, y los valores pueden ser cualquier cosa que se pueda comparar por igualdad.
Un ejemplo
Busca 4 en 5, 1, 4, 2, 8. ¿5 es igual a 4? No. ¿Y 1? No. ¿Y 4? Sí: encontrado en la posición 3 tras 3 comparaciones. Ahora busca 7 en la misma lista. Se revisa cada uno de los cinco valores y ninguno coincide, así que tras 5 comparaciones la respuesta es que 7 no está.
Cuántas comparaciones
Encontrar un valor en la posición k cuesta k comparaciones. Si el valor buscado tiene la misma probabilidad de estar en cualquier posición, son (n + 1)/2 comparaciones de media: 20,5 para 40 valores. Un valor ausente siempre cuesta n, porque solo tras la última comparación es seguro que ningún valor coincidía. Así que el coste crece en proporción a la longitud de la lista, lo que se escribe O(n).
Buscar más rápido requiere orden
La búsqueda lineal no puede saltarse nada, porque en una lista sin ordenar cualquier valor puede estar en cualquier sitio. Cuando la lista está ordenada, una comparación dice más que igual o no: dice en qué lado está el valor buscado. La búsqueda binaria lo aprovecha para partir la lista por la mitad en cada paso y necesita unas log₂ n comparaciones, como mucho 6 para 40 valores. Pero ordenar también lleva tiempo, así que para una lista en la que solo se busca una vez, la búsqueda lineal suele ser la mejor opción.
Pequeñas mejoras
Una versión con centinela coloca el valor buscado al final de la lista antes de buscar, así el bucle solo tiene que comprobar si hay coincidencia y no también si ha llegado al final. Adelantar un valor un lugar, o llevarlo al principio, cada vez que se encuentra abarata con el tiempo los valores que se buscan a menudo. Ninguna de las dos cambia el peor caso de n comparaciones.
Pruébalo
Abre la aplicación, elige un valor en Buscar y pulsa Paso. La línea discontinua muestra la altura del valor buscado, cada valor se resalta mientras se revisa y se atenúa al descartarse, y una coincidencia se vuelve verde. Busca un valor que no está en la lista para ver un recorrido completo, o desactiva «Parar en la primera coincidencia» y elige Pocos valores distintos para encontrar varias coincidencias.
Preguntas frecuentes
¿Cuál es la complejidad temporal de la búsqueda lineal?
O(n) en el peor caso y en el caso medio, y O(1) en el mejor caso, cuando el valor buscado es el primero. No necesita memoria adicional.
¿Qué diferencia hay entre la búsqueda lineal y la binaria?
La búsqueda lineal revisa cada valor en orden y funciona con cualquier lista. La búsqueda binaria solo funciona con una lista ordenada, pero en cada paso parte por la mitad la zona que puede contener el valor buscado, así que necesita unas log₂ n comparaciones en lugar de hasta n.
¿La búsqueda lineal necesita una lista ordenada?
No. Esa es su principal ventaja. En una lista ordenada puede parar en cuanto pasa la posición donde debería estar el valor buscado, pero sigue siendo más lenta que la búsqueda binaria.
¿Dónde se usa la búsqueda lineal?
Allí donde las listas son cortas o están sin ordenar: encontrar un elemento en un array pequeño, recorrer un archivo o un flujo que solo se puede leer en orden, o comprobar una condición en cada elemento. Muchas funciones de biblioteca, como indexOf en JavaScript y list.index en Python, son búsquedas lineales.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la búsqueda lineal