A procura por um valor
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.
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.
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.
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)```