Problemas algorítmicos de búsqueda

9.1 Ejemplos de problemas resueltos con búsqueda lineal y binaria

Búsqueda lineal

Problema de búsqueda de un elemento en un array: Se da un array de números y un valor objetivo. Es necesario encontrar el índice del valor objetivo en el array.

Solución: Usamos búsqueda lineal para verificar cada elemento del array.

Ejemplo de implementación:

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

# Ejemplo de uso:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Salida: 2

Búsqueda binaria

Problema de búsqueda de un elemento en un array ordenado: Se da un array ordenado de números y un valor objetivo. Es necesario encontrar el índice del valor objetivo en el array.

Solución: Usamos búsqueda binaria para dividir el array en mitades y buscar el valor objetivo.

Ejemplo de implementación:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Ejemplo de uso:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Salida: 3

9.2 Problemas sobre el uso de tablas hash para optimizar la búsqueda

1. Búsqueda de duplicados en un array

Problema: Se da un array de números. Es necesario encontrar y devolver todos los duplicados en el array.

Solución: Usamos una tabla hash para rastrear los números que ya han aparecido. Si un número aparece de nuevo, lo añadimos a la lista de duplicados.

Ejemplo de implementación:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Ejemplo de uso
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Salida: [2, 4]

2. Encontrar pares con una suma dada

Problema: Se da un array de números y un valor objetivo de suma. Es necesario encontrar todos los pares de números que suman el valor objetivo.

Solución: Usamos una tabla hash para almacenar los números y verificar si forman un par con el número actual que da la suma objetivo.

Ejemplo de implementación:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Ejemplo de uso
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Salida: [(1, 5), (7, -1), (1, 5)]

9.3 Uso combinado de diferentes métodos de búsqueda

En problemas complejos a menudo es necesario usar varios métodos de búsqueda para lograr la mejor eficiencia. El uso combinado de búsqueda lineal, búsqueda binaria y tablas hash permite resolver problemas de manera más eficiente y flexible.

Ejemplo 1: Búsqueda de un elemento en un array y verificación de su existencia en otro array

Se dan dos arrays de números. Es necesario encontrar los elementos del primer array que existen en el segundo array.

Solución:

• Usamos una tabla hash para almacenar los elementos del segundo array.
• Para cada elemento del primer array verificamos su existencia en la tabla hash.

Ejemplo de implementación:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # Tabla hash para el segundo array
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# Ejemplo de uso:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Salida: [3, 4, 5]

Ejemplo 2: Verificación de si un subarray es un anagrama del array usando una tabla hash

Se da un array de cadenas y una cadena patrón. Es necesario verificar si alguna subcadena del array es un anagrama del patrón.

Solución:

• Usamos una tabla hash para contar la frecuencia de caracteres en el patrón.
• Recorremos el array de cadenas y usamos una "ventana deslizante" para verificar cada subcadena sobre las frecuencias de caracteres.

Ejemplo de implementación:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# Ejemplo de uso:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Salida: True

9.4 Ejercicios prácticos para reforzar el material

Ejercicio 1: Búsqueda de un elemento en un array no ordenado

Se da un array de números y un valor objetivo. Es necesario encontrar el índice del valor objetivo en el array. Usa búsqueda lineal.

Ejemplo:

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

# Ejemplo de uso:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Salida: 2

Ejercicio 2: Búsqueda de duplicados en un array

Se da un array de números. Encuentra y devuelve todos los duplicados en el array utilizando una tabla hash.

Ejemplo:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Ejemplo de uso:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Salida: [3, 1]