Linear Scan, también conocido como búsqueda secuencial, es el algoritmo de búsqueda más simple. Consiste en recorrer una colección de datos (como un array, una lista enlazada o una tabla) elemento por elemento, comparando cada uno con el valor objetivo. El proceso continúa hasta que se encuentra una coincidencia o se han examinado todos los elementos de la colección. Su complejidad temporal es O(n) en el peor y caso promedio, ya que en el peor de los casos, el elemento buscado es el último o no está presente, requiriendo 'n' comparaciones. Su complejidad espacial es O(1), ya que solo requiere una cantidad constante de espacio adicional.
A pesar de su simplicidad y complejidad O(n), Linear Scan se utiliza en el mundo real en escenarios donde la colección de datos es pequeña, no está ordenada, o cuando la sobrecarga de mantener una estructura de datos más compleja o un índice es mayor que el beneficio de una búsqueda más rápida. Ejemplos incluyen: la búsqueda de un proceso específico en la lista de procesos activos del sistema operativo (cuando la lista es corta), la iteración sobre los elementos de un 'hash table' para resolver colisiones (aunque la búsqueda inicial es O(1) en promedio), o la búsqueda de un 'opcode' en una tabla de instrucciones en compiladores JIT (Just-In-Time) para arquitecturas con conjuntos de instrucciones pequeños y fijos. También es fundamental en la implementación de algoritmos más complejos, como la fase de 'mark' en algunos 'Garbage Collectors' (GC) que recorren el grafo de objetos.
Para un Arquitecto de Sistemas, entender Linear Scan es crucial para evaluar trade-offs. Aunque es ineficiente para grandes volúmenes de datos, su simplicidad y baja sobrecarga lo hacen ideal para colecciones pequeñas o cuando la latencia de acceso a la memoria es un factor dominante (cache locality). En sistemas distribuidos, un Linear Scan sobre una pequeña lista de nodos puede ser más eficiente que coordinar una búsqueda indexada si los costos de red y consenso son altos. Un arquitecto debe considerar si la simplicidad de implementación, la ausencia de requisitos de ordenación y el bajo consumo de memoria son más valiosos que la velocidad de búsqueda para un caso de uso específico. Por ejemplo, en un 'microservice' que mantiene una pequeña caché de configuración, un Linear Scan podría ser preferible a una estructura de datos más compleja para evitar la sobrecarga de mantenimiento y garantizar la predictibilidad del rendimiento en el peor de los casos.