Considere um conjunto de 65.536 chaves ordenadas, distintas ...

Alternativa correta: B

Vamos entender como chegamos a essa conclusão.

O tema central da questão é a busca binária, uma técnica de busca eficiente em um array ordenado. A busca binária funciona dividindo repetidamente o intervalo de busca pela metade, até que o elemento desejado seja encontrado ou que o intervalo de busca se torne vazio.

A busca binária tem uma complexidade de tempo de O(log₂ n), onde n é o número de elementos no array. Isso significa que, em cada passo, a busca binária reduz pela metade o número de elementos restantes a serem considerados.

Para um array contendo 65.536 chaves, devemos calcular quantas vezes podemos dividir esse número por 2 até chegarmos a 1. Essa é a essência do logaritmo binário.

Vamos calcular log₂ 65.536:

log₂ 65.536 = 16

Portanto, o número máximo de acessos ao array para localizar uma chave usando busca binária é 16. Logo, a alternativa correta é B - 16.

Agora, vamos justificar por que as outras alternativas estão incorretas:

A - 10: Esse valor é muito baixo para a quantidade de elementos dada (65.536). Um valor de 10 corresponderia a log₂ 1024, que é muito menor do que 65.536.

C - 64: Esse valor é muito alto. Log₂ 64 é 6, e log₂ 65.536 é 16. Portanto, 64 acessos são desnecessários.

D - 256: Esse valor é também extremamente alto. 256 acessos implicariam em log₂ 2²⁵⁶, o que seria um número astronômico de chaves, muito além de 65.536.

E - 32.768: Esse valor é exageradamente alto. Log₂ 32.768 é aproximadamente 15, mas o valor 32.768 acessos não faz sentido dentro do contexto da busca binária e da quantidade de chaves fornecida.

Dessa forma, ao entender a relação entre a busca binária e a redução progressiva do intervalo de busca, fica claro que a alternativa correta é B - 16.

Uma Busca binária procura, por meio da divisão do Array por 2 (dois), até encontrar uma chave/valor qualquer, ou seja, 2 elevado a 16 é igual 65.536.

2^n = 65.536

n = 16

É uma interpretação minha, mas talvez ajude a entender a busca binária.

A principal característica dessa busca é que os elementos devem estar ordenados. Partindo desta premissa, a gente pode classificar esse método como "Dividir e Conquistar".

O que isso quer dizer? Vou dividir a minha lista em 2 partes e encontrar o meio dela. Pergunta: o elemento do meio é o número que estou procurando? Se sim, não há mais nada o que fazer. Achamos o elemento logo de cara e temos uma complexidade de O(1).

Se não for, aí precisamos perguntar: o elemento que estou procurando é menor ou maior que valor que achei relativo ao meio? Se for maior, a gente vai procurar o nosso elemento na parte da direita. Se for menor, a gente vai buscar o elemento na parte da esquerda.

Aí, percebam que essa característica de "Dividir e Conquistar" vai se repetir até você achar o número que quer. No pior dos casos O(log n), você vai dividir até chegar em 1 ou próximo disso e encontrar seu número desejado.

A fórmula seria algo do tipo:

médio = menor + (maior - menor) / 2

Sendo:

médio: o elemento do meio

menor: o menor elemento do universo em que está trabalhando

maior: o maior elemento do universo em que está trabalhando

Pegando o número que a questão deu como exemplo: 65.536

65.536 / 2 = 32.768 (1º tentativa)

Achamos o número? Não. Então continuamos

Só um adendo, aqui você já conseguiria eliminar a letra "E", pois ela é o melhor caso e questão quer o pior.

32.768 / 2 = 16.384 (2º tentativa)

16.384 / 2 = 8.192 (3º tentativa)

8.192 / 2 = 4.096 (4º tentativa)

4.096 / 2 = 2.048 (5º tentativa)

2.048 / 2 = 1.024 (6º tentativa)

1.024 / 2 = 512 (7º tentativa)

512 / 2 = 256 (8º tentativa)

256 / 2 = 128 (9º tentativa)

128 / 2 = 64 (10º tentativa)

64 / 2 = 32 (11º tentativa)

32 / 2 = 16 (12º tentativa)

16 / 2 = 8 (13º tentativa)

8 / 2 = 4 (14º tentativa)

4 / 2 = 2 (15º tentativa)

2 / 2 = 1 (16º tentativa)

Dessa forma, no pior dos casos O(log n), eu precisaria de 16 tentativas para achar o número. Logo, o GAB é LETRA "B".

Repito pessoal, essa forma leiga de entender essa questão. Ela pode conter erros.

A função matemática que descreve o comportamento da busca binária em árvores binárias (o número de vezes que reduzimos pela metade de forma repetida, começando em n, até conseguirmos o valor de 1) é: logarítmo de n na base 2.

Para o problema específico temos:

- logarítmo de 65.536 na base 2 (deve-se notar que a base 2 deve-se ao fato de ser uma busca binária)

Dado que as função logarítmicas são o inverso das funções exponenciais, então temos que:

- logarítmo de 65.536 na base 2 === 2^n = 65.536

Logo, podemos concluir que n = 16

2^10 = 1024

2^11 = 2048

2^12 = 4096

2^13 = 8k // ficou difícil, perder tempo pra quê moço !!!

2^14 = 16k

2^15 = 32k

2^16=64k => 65.536!!!

2^17=128k