Question

No processo de pesquisa binária em um vetor ordenado, osnúmeros máximos de comparações necessárias para sedeterminar se um elemento faz parte de vetores com tamanhos50, 1.000 e 300 são, respectivamente, iguais aA 5, 100 e 30.B 6, 10 e 9.C 8, 31 e 18.D 10, 100 e 30.E 25, 500 e 150

#ENADE

Answer 1

Podemos afirmar então que a alternativa correta é a letra b) 6, 10 e 9.

Vamos aos dados/resoluções;

É de conhecimento público que a busca binária requer cerca de log2 n comparações para verificar se um elemento faz parte de um vetor de tamanho n:

log2 50 ≅ 5,6

log2 1000 ≅ 9,9

log2 300 ≅ 8,2

Portanto, você poderá estimar o valor do logaritmo verificando o expoente das potências de 2 mais próximas de 50, 1.000 e 300, pois a base do logaritmo em questão é igual a 2, logo:

32 < 50 < 64 ou 2^5< 50 < 2^6

512 < 1000 < 1024 ou 2^9 < 1000 < 2^10

256 < 300 < 512 ou 2^8 < 300 < 2^9.

Se analisarmos os expoentes, veremos que log2 50 está entre 5 e 6, log2 1000 está entre 9 e 10 e, finalmente, log2 300 está entre 8 e 9. Perceba que as estimativas estão de acordo com os resultados calculados anteriormente.

espero ter ajudado nos estudos, bom dia :)