Búsqueda lineal en Python: Guía para principiantes con ejemplos

Cuando se trata de algoritmos de búsqueda, la búsqueda lineal es uno de los más sencillos. Si alguna vez has mirado una lista de elementos uno por uno hasta encontrar lo que buscabas, ¡entonces ya has hecho una búsqueda lineal!

Además de ser fácil de entender, la búsqueda lineal es útil porque funciona con datos no ordenados, a diferencia de otros algoritmos de búsqueda. Esta versatilidad la convierte en una opción útil en situaciones en las que no es posible ordenar los datos. En este tutorial utilizaré Python, así que, si antes de empezar quieres refrescar tus conocimientos sobre Python, consulta el tema sobre habilidades de programación en Python.

¿Qué es la búsqueda lineal?

La búsqueda lineal es un algoritmo que localiza un valor concreto dentro de una lista comprobando cada elemento uno a uno. Empieza por el primer elemento, lo compara con el objetivo y sigue moviéndose por la lista hasta que encuentra el objetivo o llega al final de la lista. Es un algoritmo sencillo e intuitivo.

La búsqueda lineal no necesita que los datos estén ordenados para funcionar, por lo que se utiliza principalmente en conjuntos de datos sin ordenar. Esto lo hace útil en situaciones en las que no es práctico ordenar, o cuando trabajas con datos en bruto. Sin embargo, esta ventaja tiene un coste: no es tan eficaz como otros algoritmos que requieren datos preclasificados.

La búsqueda lineal es ideal en situaciones en las que trabajas con conjuntos de datos relativamente pequeños o cuando ordenar los datos no es factible. El diagrama siguiente ofrece una explicación simplificada.

Elegir la búsqueda lineal

Veamos las ventajas y también un claro inconveniente: 

¿Por qué elegir la búsqueda lineal?

En mi opinión, la búsqueda lineal tiene tres ventajas distintas:

Cuando la clave es la sencillez

Una de las mayores ventajas de la búsqueda lineal es su sencillez. El algoritmo es fácil de entender y aplicar. No hay que preocuparse de complejas ordenaciones o divisiones de los datos. Simplemente empieza por el principio de la lista y comprueba cada elemento hasta que encuentres lo que buscas.

Cuando no tienes tiempo para ordenar

A diferencia de otros algoritmos de búsqueda, como la búsqueda binaria, la búsqueda lineal no requiere que el conjunto de datos esté ordenado. Esto lo hace perfecto para cuando necesites encontrar algo rápidamente.

Cuando necesitas versatilidad

Otra ventaja de la búsqueda lineal es que es versátil. No sólo funciona con matrices, sino también con otras estructuras de datos de Python, como las listas enlazadas. Mientras puedas acceder secuencialmente a los elementos, la búsqueda lineal puede hacer el trabajo. Es lo suficientemente flexible como para manejar distintos tipos de datos, desde números a cadenas, e incluso objetos.

¿Por qué pensar dos veces en la búsqueda lineal?

Hay una cuestión a tener en cuenta:

Cuando la eficiencia importa

El principal inconveniente de la búsqueda lineal es su ineficacia, especialmente con grandes conjuntos de datos. Su complejidad temporal es O(n), lo que significa que, en el peor de los casos, ¡tendrías que comprobar cada uno de los elementos de la lista! Esto puede ralentizar mucho las cosas si trabajas con miles o millones de entradas. Sin embargo, para conjuntos de datos pequeños, esta ineficacia puede ser insignificante.

Implementar un algoritmo de búsqueda lineal en Python

En Python, hay dos formas habituales de escribir una búsqueda lineal: el método iterativo y el método recursivo. Para demostrar estos dos métodos, vamos a crear primero un conjunto de datos sencillo de 100 números sin duplicados.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]

Método iterativo

El enfoque iterativo es probablemente la forma más fácil de entender la búsqueda lineal. Recorre la lista en bucle, comprobando cada elemento hasta que encuentres el objetivo o llegues al final.

En primer lugar, crearemos nuestra función:

1. Recorreremos en bucle cada elemento de la lista arr.

2. Compararemos cada elemento con el objetivo.

3. Si encontramos una coincidencia, devolvemos el índice donde se encontró el objetivo.

4. Si terminamos el bucle sin encontrar el objetivo, devolvemos 1 para indicar que el elemento no está presente.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not found

A continuación, ejecutaremos nuestra función en nuestro conjunto de datos e imprimiremos el resultado:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")

Ejecutando este código, encontramos el valor objetivo en el elemento 23.

Método recursivo

El método recursivo utiliza una función que se llama a sí misma para buscar en la lista. Cada llamada recursiva procesa un elemento cada vez y luego pasa al siguiente. Esto continúa hasta que se encuentra el objetivo o se llega al final de la lista.

Vamos a crear nuestra función recursiva:

1. Empezaremos comprobando el primer elemento (en el índice 0).
2. Si el objetivo coincide, devolveremos el índice.
3. Si el objetivo no coincide, llamaremos a la misma función recursivamente, pero incrementando el índice en 1 para comprobar el siguiente elemento.
4. La recursión continúa hasta que encontremos el objetivo o lleguemos al final de la lista.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next element

Podemos utilizar el mismo código anterior para ejecutar esta función y nos devolverá el mismo valor de índice para nuestro objetivo: 23.

Ten en cuenta que este enfoque utiliza más memoria porque cada llamada recursiva añade una nueva capa a la pila de llamadas. Consulta Comprender las funciones recursivas en Python para conocer más a fondo la recursividad.

Complejidad temporal y espacial

Una forma de evaluar la eficacia de un algoritmo es fijarse en su complejidad temporal y espacial. Consulta el tutorial Analizar la complejidad del código mediante Python para ver las distintas formas de medir la complejidad de un algoritmo.

Complejidad temporal

La complejidad temporal de un algoritmo se refiere a cómo aumenta el tiempo que tarda en completarse a medida que crece el tamaño de la entrada. La complejidad temporal de la búsqueda lineal es O(n), donde n es el número de elementos de la lista. Esto significa que, en el peor de los casos, el algoritmo puede tener que comprobar cada uno de los elementos antes de encontrar el objetivo (o determinar que el objetivo no está en la lista). Esto es bastante ineficaz, especialmente para grandes conjuntos de datos. Por eso la búsqueda lineal funciona mejor cuando tenemos conjuntos de datos más pequeños, sin ordenar, en los que sólo tenemos que buscar una vez.

Complejidad espacial

La complejidad espacial de un algoritmo es una medida de cuánta memoria necesita a medida que crece el tamaño de la entrada. La complejidad espacial del algoritmo de búsqueda lineal depende del método que utilicemos. Para el método iterativo, la complejidad espacial es O(1), lo que significa que el algoritmo requiere una cantidad constante de memoria, independientemente del tamaño de la lista de entrada. Esto se debe a que la versión iterativa no requiere memoria adicional, aparte de la lista de entrada y unas cuantas variables para llevar la cuenta del índice actual.

Para el método recursivo, la complejidad espacial es O(n), lo que significa que la memoria necesaria crece linealmente con el tamaño de la lista de entrada. Esto se debe a las llamadas a funciones recursivas, que añaden capas a la pila de llamadas por cada elemento de la lista. Una lista más grande requiere más memoria para almacenar esas llamadas, lo que hace que el enfoque recursivo sea menos eficiente en términos de espacio.

Aplicaciones reales de la búsqueda lineal

Aunque la búsqueda lineal puede no ser el algoritmo más eficiente para grandes conjuntos de datos, tiene usos prácticos en muchos escenarios. Veamos algunas situaciones en las que la búsqueda lineal es la mejor herramienta para el trabajo.

Conjuntos de datos pequeños en los que la clasificación no es práctica

A menudo recurro a la búsqueda lineal cuando se trata de conjuntos de datos pequeños que no merecen la pena ni por tiempo ni por recursos. En estos casos, la sencillez de la búsqueda lineal puede ser más eficaz que la sobrecarga que supone ordenar los datos para algoritmos de búsqueda más complejos.

Encontrar la primera aparición de un objetivo

Otro caso de uso común de la búsqueda lineal es cuando necesitas encontrar la primera aparición de un valor objetivo. Como la búsqueda lineal recorre la lista elemento a elemento, encuentra de forma natural la primera instancia del objetivo y devuelve su posición. Esto puede ser especialmente útil en casos como buscar en una cadena la primera aparición de un carácter.

Cuando se necesita una configuración mínima

A veces, la sencillez de la búsqueda lineal la convierte en la mejor opción. Por ejemplo, si buscas rápidamente datos que no esperas reutilizar o necesitas una respuesta rápida, la configuración mínima de la búsqueda lineal puede ahorrarte tiempo.

Búsqueda lineal vs. Otros algoritmos de búsqueda

La búsqueda lineal es sólo uno de los muchos algoritmos de búsqueda que existen. Veamos otros dos algoritmos de búsqueda habituales: la búsqueda binaria y la búsqueda hash.

Búsqueda lineal vs. búsqueda binaria

La búsqueda binaria es un algoritmo que encuentra la posición de un valor objetivo dentro de una matriz ordenada dividiendo repetidamente el intervalo de búsqueda por la mitad. Tiene una complejidad temporal de O(log n), lo que la hace mucho más eficaz que la búsqueda lineal. Sin embargo, sólo funciona con datos ordenados. Cuando tu conjunto de datos está ordenado, la búsqueda binaria es casi siempre la mejor opción, porque reduce el espacio de búsqueda a la mitad en cada paso, reduciendo drásticamente el número de comparaciones necesarias para encontrar el objetivo.

La búsqueda lineal puede ser más adecuada en situaciones en las que tus datos no estén ordenados, ya que la búsqueda lineal funciona en cualquier conjunto de datos, ordenado o no. Sin embargo, con una complejidad temporal de O(n), la búsqueda lineal es mucho menos eficiente en conjuntos de datos ordenados.

Búsqueda lineal vs. búsqueda hash

La búsqueda hash es un método que utiliza una tabla hash para encontrar rápidamente un elemento. Con una complejidad temporal de O(1), es significativamente más rápido que la búsqueda lineal o binaria. Sin embargo, esta velocidad tiene un coste: primero tienes que construir una tabla hash, lo que requiere tiempo y memoria adicional. Las búsquedas Hash funcionan mejor cuando necesitas buscar en grandes conjuntos de datos varias veces, de modo que la configuración inicial compense con el tiempo.

En cambio, la búsqueda lineal no requiere configuración, por lo que es una opción más sencilla. Es la mejor opción cuando sólo necesitas buscar una vez o unas pocas veces, donde el tiempo extra para configurar una tabla hash no está justificado. La búsqueda lineal también puede ocupar menos espacio porque no necesitas almacenar una tabla hash para utilizar el algoritmo.

Errores comunes y cómo evitarlos

Aunque la búsqueda lineal es un algoritmo sencillo, hay que tener cuidado con algunos errores comunes.

Errores puntuales en la iteración

Uno de los errores más frecuentes al realizar una búsqueda lineal es el error de fuera-por-uno. Esto se debe a que la iteración se inicia o se detiene en un índice incorrecto. Es importante recordar que las listas de Python tienen índice cero, lo que significa que el primer elemento tiene índice 0. Olvidar esto puede hacer que te saltes accidentalmente el primer elemento o que iteres un paso de más, lo que puede dar lugar a resultados incorrectos o a errores.

Malinterpretar el índice devuelto

Otro error frecuente es no entender qué devuelve la función cuando no se encuentra el objetivo en la lista. Por convención, muchos algoritmos de búsqueda (incluida la búsqueda lineal) devuelven -1 para indicar que el objetivo no está presente. Sin embargo, algunos principiantes podrían suponer que devuelve None, False, o algún otro valor, lo que llevaría a confusión a la hora de interpretar los resultados.

Cuándo no utilizar la búsqueda lineal

Como hemos dicho antes, la búsqueda lineal se vuelve rápidamente ineficaz para conjuntos de datos más grandes. Por esta razón, es mejor reservarlo para conjuntos de datos pequeños y sin clasificar o para búsquedas rápidas y puntuales.

Conclusión

Como uno de los métodos de búsqueda más sencillos, la búsqueda lineal comprueba cada elemento de una lista secuencialmente, lo que hace que sea fácil de entender y aplicar. La búsqueda lineal es una opción fiable para búsquedas rápidas y puntuales en conjuntos de datos pequeños, sobre todo cuando los datos no están ordenados.

Si te interesan los algoritmos de búsqueda, consulta mis otros artículos de esta serie: Búsqueda binaria en Python, Búsqueda en profundidad en Python y Búsqueda en amplitud en Python. También te puede interesar Árbol AVL: Guía Completa Con Implementación En Python e Introducción al Análisis de Redes en Python como temas más avanzados.