Questão 3030748

• Banca: IDECAN
• Órgão: IF-PB
• Ano: 2019
• Provas: IDECAN - 2019 - IF-PB - Professor - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

Basicamente, existem dois métodos de pesquisa em um vetor de números, a Busca Linear e a Busca Binária. A Busca Binária é mais eficiente do que a Busca Linear, mas ela só funciona se o vetor estiver ordenado. Assinale a alternativa que indique a ordem de complexidade do pior caso da Busca Binária em um vetor de n números ordenados.

• A. O(n)
• B. O(n log n)
• C. O(log n)
• D. O(1)
• E. O(n^2)

Gabarito: C

Comentários

• pior caso: sempre é o O(log n)

• Em busca binária, teremos:

  Pior caso: O(log n)

  Caso médio: O(log n)

  Melhor caso: 1

  GABARITO ALTERNATIVA C

• DICA IMPORTANTE! Se o algoritmo divide por 2, a complexidade possui log

• Força Guerreiro!!!!!!