Considere que na Defensoria há uma lista ordenada com o nome de 1000 cidadãos amazonenses. Utilizando o método de pesquisa binária para localizar o nome de um destes cidadãos, serã

Gabarito

B

Comentário do professor

A busca binária reduz pela metade a lista a cada comparação: compara o elemento do meio e elimina metade dos candidatos.

No pior caso, após \(k\) comparações o número de elementos restantes é no máximo \(\frac{n}{2^k}\). Queremos chegar a, no máximo, um candidato, isto é \(\frac{n}{2^k}\le 1\), o que implica \(2^k\ge n\).

Portanto o número mínimo de comparações necessárias no pior caso é \(k=\lceil \log_2(n)\rceil\). Para \(n=1000\), \(\log_2(1000)\approx 9{,}966\), e assim \(\lceil 9{,}966\rceil=10\).

Logo, serão necessárias, no máximo 10 comparações.