Questão de Algoritmos e Estrutura de Dados — Lógicas de Programação — FGV 2018

Busca binária: número máximo de palpites

Gabarito: letra B (6). No jogo em que um número entre 1 e 32 deve ser adivinhado com dicas de "maior" ou "menor", a estratégia ótima é a busca binária. O número máximo de palpites necessários no pior caso é dado por $\lfloor \log_2 N \rfloor + 1$, onde $N = 32$. Como $\log_2 32 = 5$, temos $5 + 1 = 6$ palpites. Uma tentativa a menos (5) só seria suficiente se o palpite exato pudesse ser encontrado sem contar a última confirmação, o que não ocorre no pior cenário.

O problema testa o entendimento de busca binária e a diferença entre o número de divisões e o número de palpites. Com 32 elementos, a busca binária divide o intervalo 5 vezes, mas exige 6 palpites no pior caso (por exemplo, quando o número é 1 ou 32).

Alternativa A — ❌ Incorreta

Afirma que o máximo é 4 palpites. Com 4 palpites, no pior caso só é possível distinguir $2^4 = 16$ números, insuficiente para cobrir 32 números. O cálculo correto mostra que são necessários 6.

Alternativa B — ✅ Correta ⟵ GABARITO

Busca binária:

Número de palpites no pior caso = $\lfloor \log_2 N \rfloor + 1$.

Para $N = 32$: $\lfloor \log_2 32 \rfloor + 1 = 5 + 1 = 6$.

Exemplo: se o número for 32, os palpites podem ser 16, 24, 28, 30, 31, 32 — 6 tentativas. Se for 1, 16, 8, 4, 2, 1 — também 6.

Alternativa C — ❌ Incorreta

Propõe 8 palpites. Esse número seria necessário para um intervalo maior ($2^8 = 256$), muito acima de 32. O valor correto é 6.

Alternativa D — ❌ Incorreta

Indica 16 palpites. Isso corresponderia a $\log_2 16 = 4$ divisões? Na verdade, 16 palpites seriam suficientes para $2^{16}$ números, não para 32. É um distrator que confunde o tamanho do intervalo com o logaritmo.

Alternativa E — ❌ Incorreta

Sugere 32 palpites, que é a busca linear (um palpite por número). A presença das pistas "maior" e "menor" permite uma estratégia muito mais eficiente (busca binária), reduzindo o máximo para 6.

Gabarito: letra B (6 palpites).