SóProvas


ID
5263951
Banca
FGV
Órgão
IMBEL
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere uma lista ordenada, contendo 20 chaves únicas, na qual seja realizada uma busca binária.
Assinale o número máximo de acessos necessários para encontrar uma determinada chave.

Alternativas
Comentários
  • 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.