Algoritmos e Estrutura de Dados · CESGRANRIO · 2018 | Questão sqc-cg013891

Busca Binária – Número Máximo de Iterações

Gabarito: letra C (10). A busca binária, a cada iteração, reduz pela metade o espaço de busca. Para um vetor de 750 elementos, o número máximo de iterações é o menor inteiro $k$ tal que $2^k > 750$ . Como $2^9 = 512$ (ainda menor que 750) e $2^{10} = 1024$ (já maior), são necessárias no máximo 10 iterações para encontrar o valor ou concluir que ele não existe. Esse valor é dado por $\lceil \log_2(750) \rceil = 10$ . A ordenação descendente não altera o número de iterações, apenas a direção da comparação.

1Vetor de 750 elementos
2Cada iteração divide ao meio
32⁹ = 512 (insuficiente)
42¹⁰ = 1024 > 750
5Máximo: 10 iterações

LEVEL · soulevel.com.br

Alternativa A – ❌ Incorreta (8)

Com 8 iterações, o algoritmo conseguiria cobrir no máximo $2^8 = 256$ elementos, insuficiente para um vetor de 750.

Alternativa B – ❌ Incorreta (9)

$2^9 = 512$ , ainda insuficiente para cobrir 750 elementos.

Alternativa C – ✅ Correta ⟵ GABARITO

$2^{10} = 1024 > 750$ , garantindo que todas as posições possam ser verificadas no pior caso.

Alternativa D – ❌ Incorreta (11)

Embora algumas implementações possam realizar um número extra de comparações (dependendo da condição de parada), o máximo teórico para busca binária pura em 750 elementos é 10, não 11.

Alternativa E – ❌ Incorreta (12)

Valor superdimensionado; não há necessidade de 12 iterações para 750 elementos.

PEGA ESSA DICA!

Para calcular o número máximo de iterações da busca binária, use a fórmula $\lceil \log_2(n+1) \rceil$ ou o menor $k$ tal que $2^k > n$ . Para $n=750$ , $2^9=512$ (faltam), $2^{10}=1024$ (suficiente). Memorize que cada iteração dobra a cobertura.

Gabarito: letra C.