Questão de Programação — Programação estruturada — FGV 2023

Pesquisa binária: contagem de execuções recursivas

Gabarito: letra A. A função bin é executada 2 vezes (incluindo a chamada inicial) para encontrar o valor 20 no vetor {4, 5, 8, 9, 14, 16, 17, 20, 23, 25}. Na primeira chamada, bin(1, 10, 20), o meio é calculado como (1+10) div 2 = 5, e como valores[5] = 14 < 20, a busca continua na metade direita com bin(6, 10, 20). Nesta segunda chamada, o meio é (6+10) div 2 = 8, e valores[8] = 20, encontrando o elemento e retornando a posição 8. Portanto, a função é executada exatamente 2 vezes.

A pesquisa binária é um algoritmo clássico de busca em estruturas ordenadas, como vetores. Seu princípio é dividir para conquistar: a cada passo, o intervalo de busca é reduzido pela metade, comparando o elemento do meio com o valor procurado. Se o valor do meio é menor que o procurado, descarta-se a metade esquerda; se é maior, descarta-se a metade direita. Esse processo se repete até encontrar o elemento ou esgotar o intervalo.

A eficiência desse algoritmo é notável: em um vetor de tamanho $n$, o número máximo de comparações é da ordem de $\log_2(n)$. Para $n = 10$, o número máximo de execuções seria cerca de $\lceil \log_2(10) \rceil = 4$, mas no caso específico do valor 20, o algoritmo converge mais rapidamente.

Vamos simular a execução passo a passo com o vetor dado:

A pegadinha desta questão está em contar corretamente as execuções da função. Muitos candidatos contam apenas as chamadas recursivas internas, esquecendo de incluir a chamada inicial. O enunciado é explícito: "incluindo a chamada inicial". Portanto, a resposta correta é 2, não 1.

Outro ponto de atenção é o cálculo do meio com divisão inteira truncando a parte decimal. Em algumas linguagens, a divisão de inteiros já trunca automaticamente; em outras, é necessário usar o operador de divisão inteira (como div ou //). Aqui, o enunciado garante que a divisão é inteira, então (1+10)/2 = 5.5 vira 5.

Alternativa A — ✅ Correta ⟵ GABARITO

A função bin é executada 2 vezes: a chamada inicial bin(1, 10, 20) e a chamada recursiva bin(6, 10, 20). Na segunda execução, o elemento é encontrado na posição 8, e a função retorna. O enunciado pede explicitamente para incluir a chamada inicial, então a contagem correta é 2.

Alternativa B — ❌ Incorreta

Afirma que a função é executada 4 vezes. Isso seria o número máximo de execuções para um vetor de 10 elementos ($\lceil \log_2(10) \rceil = 4$), mas não é o caso específico do valor 20, que é encontrado na segunda tentativa. O candidato que marca esta opção provavelmente confundiu o pior caso com o caso específico do enunciado.

Alternativa C — ❌ Incorreta

Afirma que a função é executada 6 vezes. Esse número não corresponde a nenhum cenário da pesquisa binária para este vetor. O número máximo de execuções para 10 elementos é 4, então 6 é um valor impossível. Provavelmente é um distrator aleatório.

Alternativa D — ❌ Incorreta

Afirma que a função é executada 8 vezes. Assim como a alternativa C, esse número excede o máximo teórico de 4 execuções para um vetor de 10 elementos. É um distrator sem fundamento.

Alternativa E — ❌ Incorreta

Afirma que a função é executada 10 vezes. Esse número corresponderia a uma busca linear, não a uma pesquisa binária. Na busca linear, cada elemento seria comparado até encontrar o valor, o que poderia levar até 10 comparações. A banca provavelmente incluiu essa opção para testar se o candidato sabe diferenciar os dois algoritmos.

Gabarito: letra A