Algoritmos de Búsqueda y Ordenación: Búsqueda Lineal en Python

¿Qué aprenderemos en el módulo de algoritmos de búsqueda y ordenación?

A lo largo de este módulo, nos enfocaremos en dos aspectos fundamentales: aplicar conceptos de complejidad algorítmica y comprender el uso de diferentes algoritmos para resolver problemas. La habilidad de transformar un problema desconocido en uno para el cual ya conocemos la solución es esencial en el campo de la ciencia de datos y el desarrollo de software. Comenzaremos con un algoritmo sencillo pero importante: la búsqueda lineal.

¿Cómo se implementa la búsqueda lineal?

La búsqueda lineal es un algoritmo básico que nos permite buscar un elemento dentro de una lista, ya sea ordenada o desordenada. Aquí te presento cómo implementar este algoritmo en Python.

def busqueda_lineal(lista, objetivo):
    match = False
    for elemento in lista:
        if elemento == objetivo:
            match = True
            break
    return match

1. Definición de Función: Creamos una función busqueda_lineal que recibe una lista y un objetivo.
2. Inicialización: Comenzamos definiendo match como False.
3. Iteración: Usamos un bucle for para recorrer cada elemento en lista.
4. Condición: Si elemento es igual a objetivo, cambiamos match a True.
5. Retorno: Devolvemos el valor de match.

¿Cómo interactuar con el usuario?

Podemos crear un programa en Python que genere listas aleatorias y pregunte al usuario por el elemento objetivo. Aquí se incluye el uso de módulos y funciones básicas de Python.

import random

if __name__ == '__main__':
    # Solicitar tamaño de la lista al usuario
    tamaño_lista = int(input("¿De qué tamaño será la lista? "))
    
    # Solicitar el objetivo que desea encontrar
    objetivo = int(input("¿Qué número quieres encontrar? "))
    
    # Generar lista de números aleatorios
    lista = [random.randint(0, 100) for _ in range(tamaño_lista)]
    print("Lista:", lista)
    
    # Buscar objetivo en la lista
    encontrado = busqueda_lineal(lista, objetivo)
    
    # Imprimir resultado
    print(f"El elemento {objetivo} {'está' if encontrado else 'no está'} en la lista")

1. Solicitar Datos: Primero, preguntamos al usuario el tamaño de la lista que desea generar y el número que quiere encontrar.
2. Generación Aleatoria: Utilizamos random.randint para poblar la lista con números aleatorios entre 0 y 100.
3. Ejecución de Búsqueda: Llamamos a busqueda_lineal para verificar si el objetivo está en la lista.
4. Impresión del Resultado: Informamos al usuario si el número fue encontrado.

¿Cuál es la complejidad algorítmica de la búsqueda lineal?

La complejidad de tiempo de la búsqueda lineal es comúnmente conocida como (O(n)), donde (n) es el tamaño de la lista. A continuación, te explico por qué:

• Bucle Único: El algoritmo hace uso de un solo bucle que recorre completamente la lista.
• Peor Escenario: El peor caso ocurre cuando el elemento deseado es el último en la lista o no está presente, lo que implica recorrer todo el conjunto.
• Mejor Escenario: El mejor de los casos sería encontrar el elemento en la primera posición, pero aún así, la complejidad sigue siendo proporcional a (n).

Si lograste derivar esta complejidad por ti mismo, ¡felicidades! Es un paso significativo en la comprensión de la complejidad algorítmica. Si no lo comprendiste completamente, no te preocupes, ya que estos pueden ser temas desafiantes. Te animo a seguir explorando y aprendiendo para dominar este concepto esencial en el desarrollo de software y la ciencia de datos.