Búsqueda Lineal

1.1 Definición de búsqueda lineal

Búsqueda lineal (también conocida como búsqueda secuencial) es un algoritmo para buscar un elemento en una lista o matriz, que verifica cada elemento de manera secuencial hasta encontrar una coincidencia o revisar todos los elementos. Este es el algoritmo de búsqueda más simple, que no requiere ordenar los datos previamente.

Principios básicos:

• Verificación secuencial: El algoritmo recorre cada elemento del array o lista, comparándolo con el valor buscado.
• Interrupción de la búsqueda: La búsqueda se detiene cuando se encuentra un elemento que coincide con el valor buscado o cuando se han verificado todos los elementos.
• No requiere ordenamiento: La búsqueda lineal puede aplicarse a datos no ordenados.
• Aplicación: La búsqueda lineal puede aplicarse a cualquier estructura de datos que soporte iteración, incluyendo listas y matrices.

La búsqueda lineal tiene una complejidad de tiempo de O(n), donde n es el número de elementos en el array o lista. En el peor de los casos, el algoritmo deberá revisar todos los n elementos para encontrar el valor buscado o determinar su ausencia.

Análisis de complejidad de tiempo:

• Mejor caso (Best case): El elemento se encuentra en el primer lugar, O(1).
• Promedio de los casos (Average case): El elemento se encuentra en algún lugar del medio, O(n/2), que es equivalente a O(n).
• Peor caso (Worst case): El elemento se encuentra en el último lugar o está ausente, O(n).

1.2 Implementación paso a paso de la búsqueda lineal

Pasos de la búsqueda lineal:

• Inicialización: Establecer el índice inicial para la búsqueda (generalmente el índice cero).
• Verificación secuencial: Verificar cada elemento de la lista o matriz para ver si coincide con el valor buscado.
• Condición de terminación: Si se encuentra el elemento, devolver su índice. Si todos los elementos se han verificado y el valor buscado no se encuentra, devolver un valor especial (generalmente -1 o None).

Implementación de la búsqueda lineal en Python:

def linear_search(arr, target):
    # Recorremos cada elemento del array
    for index, element in enumerate(arr):
        # Si el elemento actual es igual al valor buscado, devolvemos su índice
        if element == target:
            return index
    # Si el elemento no se encuentra, devolvemos -1
    return -1

Explicación paso a paso de la implementación:

• Inicialización del bucle: Se utiliza un bucle for con la función enumerate, que devuelve el índice y el elemento del array en cada iteración.
• Comparación: En cada iteración, el elemento actual se compara con el valor buscado (target).
• Devolver índice: Si el elemento actual es igual al valor buscado, se devuelve el índice de ese elemento.
• Devolver -1: Si el bucle finaliza y el elemento buscado no se encuentra, se devuelve -1.

# Ejemplo de uso:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 7 encontrado en el índice 2

# Ejemplo de uso para un elemento que no está en el array:
target = 5
result = linear_search(arr, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 5 encontrado en el índice -1

1.3 Ejemplos de problemas resueltos con búsqueda lineal

La búsqueda lineal se utiliza para resolver muchos problemas relacionados con la búsqueda de elementos en colecciones de datos. Aquí hay algunos ejemplos de tales problemas:

Problema 1: Buscar un elemento en un array

Necesitas encontrar un número dado en un array de números.

Ejemplo:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Elemento {target} encontrado en el índice {index}")  # Salida: Elemento 70 encontrado en el índice 3

Problema 2: Comprobar la presencia de un elemento en una lista

Necesitas comprobar si un valor dado está presente en una lista de cadenas.

Ejemplo:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Elemento {target} {'encontrado' if found else 'no encontrado'}")  # Salida: Elemento cherry encontrado

Problema 3: Buscar el elemento mínimo o máximo

Necesitas encontrar el valor mínimo o máximo en una lista.

Ejemplo:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Valor mínimo: {min_value}")  # Salida: Valor mínimo: 2

Problema 4: Buscar la primera aparición

Encontrar la primera aparición de un elemento dado en una lista.

Ejemplo:

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Primera aparición de {target} en el índice {index}")  # Salida: Primera aparición de 2 en el índice 1

Problema 5: Contar el número de ocurrencias

Contar el número de veces que un elemento dado aparece en una lista.

Ejemplo:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Elemento {target} encontrado {count} veces")  # Salida: Elemento 2 encontrado 3 veces