Busca binária recursiva

3.1 Princípio de funcionamento da busca binária recursiva

Busca binária — é um algoritmo para encontrar um elemento em um array ordenado, que funciona no princípio de "dividir e conquistar". Ele compara o elemento procurado com o elemento no meio do array e decide em qual metade do array continuar a busca. A busca binária recursiva repete esse processo chamando a si mesmo com os limites atualizados do array.

Passos do algoritmo:

1. Compara o elemento procurado com o elemento no meio do array.
2. Se o elemento no meio é o procurado, retorna seu índice.
3. Se o elemento procurado é menor, repete a busca na metade esquerda do array.
4. Se o elemento procurado é maior, repete a busca na metade direita do array.
5. Repete o processo até encontrar o elemento ou esgotar o array.

Implementação da busca binária recursiva

Exemplo em Python:

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Caso base: elemento não encontrado
            
    mid = (left + right) // 2  # Encontrando o meio do array
            
    if arr[mid] == target:
        return mid  # Caso base: elemento encontrado
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # Procurar na metade direita
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # Procurar na metade esquerda
        
# Exemplo de uso:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Elemento encontrado na posição: {result}")  # Vai imprimir: Elemento encontrado na posição: 6
        

3.2 Comparação com a busca binária iterativa

Busca binária iterativa:

def binary_search_iterative(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  # Elemento não encontrado
        
# Exemplo de uso:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)
print(f"Elemento encontrado na posição: {result}")  # Vai imprimir: Elemento encontrado na posição: 6
        

Comparação:

Simplicidade de implementação:

• O algoritmo recursivo geralmente é mais simples e curto, mas requer o entendimento das chamadas recursivas.
• O algoritmo iterativo usa um loop, o que pode ser mais fácil para programadores iniciantes.

Memória:

• O algoritmo recursivo usa a pilha de chamadas, o que pode aumentar o uso de memória em arrays grandes.
• O algoritmo iterativo usa uma quantidade constante de memória, tornando-o mais eficiente em termos de uso de memória.

Desempenho:

• Ambos os algoritmos têm complexidade de tempo O(log n).
• O algoritmo recursivo pode ser mais lento devido ao custo das chamadas recursivas, especialmente se a profundidade da recursão for grande.

3.3 Exemplos de problemas para busca binária recursiva

A busca binária recursiva é um algoritmo poderoso que ajuda a encontrar rapidamente elementos em arrays ordenados. Ele se baseia no princípio de "dividir e conquistar" e usa a recursão para dividir a tarefa em sub-tarefas menores.

A comparação entre as abordagens recursiva e iterativa mostra que cada uma tem suas vantagens e desvantagens dependendo da tarefa específica. Compreender esses algoritmos e suas aplicações permite resolver de forma eficaz problemas de busca em programação.

Por exemplo, tais como:

Busca de um elemento em um array ordenado:

Procurar um elemento específico em um array de números, como avaliação de testes, busca em banco de dados por chaves ordenadas e assim por diante.

Verificação da presença de um elemento:

Verificar se um determinado valor está presente em uma lista de usuários autorizados, identificadores e assim por diante.

Busca do valor mais próximo:

Procurar o elemento mais próximo de um determinado valor em um array, por exemplo, ao procurar a loja mais próxima, estação e assim por diante.

Otimização:

Resolver tarefas que exigem a busca de um valor ótimo em um array ordenado, como encontrar o ponto de mínimo ou máximo em funções.