A procura por um valor k em um vetor ordenado v pode ser feita eficientemente pelo seguinte algoritmo:
Seja m o valor do elemento que ocupa a posição "central" no vetor.
Se k=m, retornar o índice de m no vetor;
Se k<m,continuar a procura apenas na primeira "metade" do vetor;
Se k>m,continuar a procura apenas na segunda "metade" do vetor.
Implementar este algoritmo como uma função recursiva.

Passo 1

O problema é implementar a busca binária (binary search) de forma recursiva em um vetor ordenado. Vamos usar a técnica de divisão e conquista, mantendo os índices limite (inicial e final) e reduzindo o intervalo a cada chamada.

Passo 2

Definimos a assinatura da função aceita quatro parâmetros: o vetor v, o valor k a ser buscado, o índice esquerdo e o índice direito que delimitam a porção ativa do vetor.

Passo 3

No início de cada chamada, checamos o caso base: se o índice esquerdo passou do direito (esquerdo > direito), significa que k não está no vetor e retornamos -1.
Caso contrário, calculamos o índice central (meio = (esquerdo + direito) // 2) e comparamos v[meio] com k. Se for igual, devolvemos meio.

Passo 4

Se v[meio] for maior que k, continuamos a busca na metade esquerda chamando a própria função com direito = meio - 1.

Passo 5

Se v[meio] for menor que k, continuamos a busca na metade direita chamando a própria função com esquerdo = meio + 1.

Resposta

def busca_binaria_rec(v, k, esquerdo, direito):
    # Caso base: intervalo inválido -> não encontrou
    if esquerdo > direito:
        return -1

    meio = (esquerdo + direito) // 2

    # Elemento encontrado
    if v[meio] == k:
        return meio
    # Se k for menor, busca na metade esquerda
    elif v[meio] > k:
        return busca_binaria_rec(v, k, esquerdo, meio - 1)
    # Se k for maior, busca na metade direita
    else:
        return busca_binaria_rec(v, k, meio + 1, direito)

# Exemplo de uso:
# índice = busca_binaria_rec(vetor_ordenado, valor_procurado, 0, len(vetor_ordenado) - 1)```

Exercícios relacionados