GabaritoB — 5
Gabarito: letra B (5). Para uma lista ordenada de 20 chaves, a busca binária descarta metade dos elementos a cada comparação. O número máximo de acessos (comparações) no pior caso é ⌊log₂(n)⌋ + 1 = ⌊log₂(20)⌋ + 1 = 4 + 1 = 5.
A busca binária é um algoritmo de divisão e conquista que reduz o espaço de busca pela metade a cada passo. Com 20 elementos, o processo é:
Comparação com o meio (10 elementos restantes)
Comparação na metade do subconjunto (5 restantes)
Comparação (2 ou 3 restantes)
Comparação (1 restante)
Última comparação confirmando a chave.
Assim, são necessários no máximo 5 acessos. As demais alternativas são incorretas:
A) 4: subestima o pior caso (log₂20 ≈ 4,32 → arredonda para 5).
C) 6, D) 10, E) 20: superestimam o número máximo; 6 seria o pior caso para 64 elementos, 10 para 1024, e 20 seria o da busca linear.
Para calcular o pior caso da busca binária, use a fórmula ⌊log₂(n)⌋ + 1. Para n=20, log₂20 ≈ 4,32 → floor 4 → +1 = 5. Esse valor equivale à altura de uma árvore binária balanceada com n folhas.
Gabarito: letra B.
Link permanente: /questoes/fg042898