-
Basicamente a busca binária é realizada através da divisão pela metade. Sabendo disso:
1ª Busca: 20 elementos
2ª Busca: 10 elementos
3ª Busca: 5 elementos
4ª Busca: 2 elementos
5ª Busca: 1 elemento
Então na pior das hipóteses, teremos que percorrer toda a lista para encontrar o elemento desejado, gastando 5 acessos.
GABARITO ALTERNATIVA B
-
Neste vídeo o Túlio Faria mostra uma implementação em JS
https://www.youtube.com/watch?v=l6pxuyV3mKQ
-
Boa Sorte
-
Excelente material para compreensão deste assunto.
https://dev.to/vapordev/complexidade-logaritmica-o-log-n-3n86
-
Para encontrar 1 elemento: 5 acessos, apenas no quinto conseguiria. Boa questão!
-
GABARITO B
Outra forma de resolver a questão é aplicando a complexidade das buscas binárias, que é O(log2 n):
n = 20 (quantidade de elementos)
log2 (20) = 4,32 -> Arredonda pra cima -> = 5
Logo, serão necessários, no máximo, 5 acessos para encontrar uma chave.