Problemas Algorítmicos de Busca

9.1 Exemplos de problemas resolvidos com busca linear e binária

Busca Linear

Problema de busca de elemento em um array: Dado um array de números e um valor alvo. É necessário encontrar o índice do valor alvo no array.

Solução: Usar a busca linear para verificar cada elemento do array.

Exemplo de implementação:

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

# Exemplo de uso:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Saída: 2

Busca Binária

Problema de busca de elemento em um array ordenado: Dado um array de números ordenado e um valor alvo. É necessário encontrar o índice do valor alvo no array.

Solução: Usar a busca binária para dividir o array ao meio e procurar o valor alvo.

Exemplo de implementação:

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

# Exemplo de uso:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Saída: 3

9.2 Problemas usando tabelas hash para otimizar buscas

1. Busca de duplicatas em um array

Problema: Dado um array de números. É necessário encontrar e retornar todas as duplicatas no array.

Solução: Usar uma tabela hash para rastrear números que já apareceram. Se um número aparecer novamente, adicioná-lo à lista de duplicatas.

Exemplo de implementação:

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

# Exemplo de uso
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Saída: [2, 4]

2. Encontrar pares com uma soma específica

Problema: Dado um array de números e um valor alvo de soma. É necessário encontrar todos os pares de números cuja soma é igual ao valor alvo.

Solução: Usar uma tabela hash para armazenar números e verificar se formam um par com o número atual que atinge a soma alvo.

Exemplo de implementação:

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

# Exemplo de uso
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Saída: [(1, 5), (7, -1), (1, 5)]

9.3 Uso combinado de diferentes métodos de busca

Em problemas complexos, muitas vezes é necessário usar vários métodos de busca para alcançar a melhor eficiência. O uso combinado de busca linear, busca binária e tabelas hash permite resolver problemas de forma mais eficaz e flexível.

Exemplo 1: Buscar elemento em um array e verificar sua existência em outro array

São dados dois arrays de números. É necessário encontrar os elementos do primeiro array que existem no segundo array.

Solução:

• Usar uma tabela hash para armazenar os elementos do segundo array.
• Para cada elemento do primeiro array, verificar sua existência na tabela hash.

Exemplo de implementação:

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

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

    return common_elements

# Exemplo de uso:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Saída: [3, 4, 5]

Exemplo 2: Verificar se uma subarray é um anagrama usando uma tabela hash

É dado um array de strings e uma string padrão. É necessário verificar se alguma substring do array de strings é um anagrama do padrão.

Solução:

• Usar uma tabela hash para contar a frequência dos caracteres no padrão.
• Percorrer o array de strings e usar uma "janela deslizante" para verificar cada substring quanto à correspondência das frequências de caracteres.

Exemplo de implementação:

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

# Exemplo de uso:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Saída: True

9.4 Exercícios práticos para fixação do material

Exercício 1: Buscar elemento em um array não ordenado

É dado um array de números e um valor alvo. É necessário encontrar o índice do valor alvo no array. Use a busca linear.

Exemplo:

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

# Exemplo de uso:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Saída: 2

Exercício 2: Buscar duplicatas em um array

É dado um array de números. Encontre e retorne todas as duplicatas no array usando uma tabela hash.

Exemplo:

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

# Exemplo de uso:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Saída: [3, 1]