Exemplos de problemas de busca linear e binária

3.1 Problema de encontrar um elemento em um array usando busca linear

Problema: Dado um array de números. É necessário encontrar o índice de um determinado número usando a busca linear. Se o número não for encontrado, retornar -1.

Exemplo:

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
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 um 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

Explicação:

• A função linear_search percorre cada elemento do array arr e compara com target.
• Se o elemento for encontrado, o índice é retornado.
• Se todos os elementos forem verificados e o valor procurado não for encontrado, a função retorna -1.

Passo a passo:

1. Array [4, 2, 7, 1, 9, 3] e valor procurado 7.
2. Início da busca: compara o primeiro elemento (4) com 7 — não corresponde.
3. Passa para o próximo elemento (2) — não corresponde.
4. Passa para o próximo elemento (7) — corresponde.
5. Retorna o índice 2.

3.2 Problema de encontrar um elemento em um array ordenado usando busca binária

Problema: Dado um array ordenado de números. É necessário encontrar o índice de um determinado número usando a busca binária. Se o número não for encontrado, retornar -1.

Exemplo:

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
result = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado no índice {result}")  # Saída: Elemento 7 encontrado no índice 3

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

Explicação:

• A função binary_search usa dois ponteiros (left e right) para acompanhar os limites da busca no array arr.
• Em cada iteração, o elemento do meio do array é encontrado e comparado com target.
• Se o elemento do meio for igual a target, seu índice é retornado.
• Se target for menor que o elemento do meio, a busca continua na metade esquerda do array.
• Se target for maior que o elemento do meio, a busca continua na metade direita do array.
• Se os limites se cruzarem e o elemento não for encontrado, retorna -1.

Passo a passo:

1. Array ordenado [1, 3, 5, 7, 9, 11, 13] e valor procurado 7.
2. Limites iniciais da busca: left = 0, right = 6.
3. Encontrar o elemento do meio: mid = (0 + 6) // 2 = 3.
4. Comparar o elemento do meio (7) com target (7) — corresponde.
5. Retornar o índice 3.

3.3 Comparação e escolha do algoritmo de busca adequado para diferentes problemas

Comparação entre busca linear e binária:

Escolha do algoritmo apropriado

Busca Linear:

• Usada quando os dados não estão ordenados.
• Adequada para arrays ou listas pequenas.
• Aplicável quando o número de elementos é pequeno e o tempo de execução não é crítico.

Busca Binária:

• Aplicada quando os dados estão ordenados.
• Ideal para arrays grandes, onde a velocidade de busca é importante.
• Eficiente se for necessária uma busca frequente no mesmo conjunto de dados (pode-se ordenar os dados previamente).

3.4 Exercícios práticos para fixar o material

Exercício 1: Busca Linear

Dado um array de números. Escreva uma função para procurar um número específico usando busca linear. A função deve retornar o índice do elemento encontrado ou -1, se o elemento não for encontrado.

Exemplo:

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
result = linear_search(arr, target)
print(f"Elemento {target} encontrado no índice {result}")  # Saída: Elemento 7 encontrado no índice 2

# Testes adicionais:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Exercício 2: Busca Binária

Dado um array ordenado de números. Escreva uma função para procurar um número específico usando busca binária. A função deve retornar o índice do elemento encontrado ou -1, se o elemento não for encontrado.

Exemplo:

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
result = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado no índice {result}")  # Saída: Elemento 7 encontrado no índice 3

# Testes adicionais:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Exercício 3: Comparação entre busca linear e binária

Dado um array de números. Escreva duas funções para procurar um número específico: uma usando busca linear e outra usando busca binária. Compare o desempenho de ambas as funções em arrays grandes.

Exemplo:

import time
import random

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

# Busca Binária
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

# Geração de um grande array
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Comparação de desempenho
start_time = time.time()
linear_search(large_array, target)
print(f"Busca Linear levou: {time.time() - start_time:.6f} segundos")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Busca Binária levou: {time.time() - start_time:.6f} segundos")