Busca Linear

1.1 Definição da Busca Linear

Busca Linear (também conhecida como busca sequencial) é um algoritmo de busca de um elemento em uma lista ou array, que verifica cada elemento sequencialmente até encontrar uma correspondência ou verificar todos os elementos. É o algoritmo de busca mais simples, que não requer ordenação prévia dos dados.

Princípios básicos:

• Verificação sequencial: O algoritmo passa por cada elemento do array ou lista, comparando-o com o valor procurado.
• Encerramento da busca: A busca termina quando um elemento correspondente ao valor procurado é encontrado ou quando todos os elementos são verificados.
• Não requer ordenação: A busca linear pode ser aplicada a dados não ordenados.
• Aplicação: A busca linear pode ser aplicada a qualquer estrutura de dados que suporte iteração, incluindo listas e arrays.

A busca linear tem uma complexidade de tempo O(n), onde n é o número de elementos no array ou lista. No pior caso, o algoritmo precisará verificar todos os n elementos para encontrar o valor procurado ou determinar sua ausência.

Análise da complexidade do tempo:

• Melhor caso (Best case): O elemento é encontrado na primeira posição, O(1).
• Caso médio (Average case): O elemento é encontrado em algum lugar no meio, O(n/2), que é equivalente a O(n).
• Pior caso (Worst case): O elemento é encontrado na última posição ou está ausente, O(n).

1.2 Implementação passo a passo da busca linear

Passos da busca linear:

• Inicialização: Definir o índice inicial para a busca (geralmente índice zero).
• Verificação sequencial: Verificar cada elemento da lista ou array para correspondência com o valor procurado.
• Condição de término: Se o elemento for encontrado, retornar seu índice. Se todos os elementos forem verificados e o valor procurado não for encontrado, retornar um valor especial (geralmente -1 ou None).

Implementação da busca linear em Python:

def linear_search(arr, target):
    # Percorre cada elemento do array
    for index, element in enumerate(arr):
        # Se o elemento atual é igual ao valor procurado, retorna o índice
        if element == target:
            return index
    # Se o elemento não foi encontrado, retorna -1
    return -1

Explicação passo a passo da implementação:

• Inicialização do loop: Usa-se o loop for com a função enumerate, que retorna o índice e o elemento do array a cada iteração.
• Comparação: Em cada iteração, o elemento atual é comparado com o valor procurado (target).
• Retorno do índice: Se o elemento atual for igual ao valor procurado, o índice desse elemento é retornado.
• Retorno -1: Se o loop terminar e o elemento procurado não for encontrado, retorna -1.

# Exemplo de uso:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Elemento {target} encontrado no índice {result}")  # Saída: Elemento 7 encontrado no índice 2

# Exemplo de uso para elemento que não está no array:
target = 5
result = linear_search(arr, target)
print(f"Elemento {target} encontrado no índice {result}")  # Saída: Elemento 5 encontrado no índice -1

1.3 Exemplos de problemas resolvidos com busca linear

A busca linear é usada para resolver uma variedade de problemas relacionados à busca de elementos em coleções de dados. Aqui estão alguns exemplos desses problemas:

Problema 1: Busca de um elemento em um array

É necessário encontrar um número específico em um array de números.

Exemplo:

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 no índice {index}")  # Saída: Elemento 70 encontrado no índice 3

Problema 2: Verificação da presença de um elemento em uma lista

É necessário verificar se um determinado valor está presente em uma lista de strings.

Exemplo:

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 'não encontrado'}")  # Saída: Elemento cherry encontrado

Problema 3: Busca do elemento mínimo ou máximo

É necessário encontrar o valor mínimo ou máximo em uma lista.

Exemplo:

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}")  # Saída: Valor mínimo: 2

Problema 4: Busca da primeira ocorrência

Encontrar a primeira ocorrência de um elemento específico em uma lista.

Exemplo:

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"Primeira ocorrência de {target} no índice {index}")  # Saída: Primeira ocorrência de 2 no índice 1

Problema 5: Contagem de ocorrências

Contar a quantidade de ocorrências de um elemento específico em uma lista.

Exemplo:

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} aparece {count} vezes")  # Saída: Elemento 2 aparece 3 vezes