Questão 3310825

• Banca: FUNDEP (Gestão de Concursos)
• Órgão: INB
• Ano: 2018
• Provas: FUNDEP (Gestão de Concursos) - 2018 - INB - Analista de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

Qual o algoritmo de busca que se baseia no princípio de dividir os dados na posição central, testando o elemento a ser encontrado com o elemento que está nessa posição (central)? Considere que, caso o elemento sendo buscado não seja o elemento central, então metade do conjunto de dados já pode ser descartado.

• A. Busca binária.
• B. Busca serial.
• C. Busca sequencial.
• D. Busca ordenada.

Gabarito: A

Comentários

• Busca Binária

  Utiliza o método do “dividir para conquistar”: busca o elemento do meio da coleção, dividindo-a em duas sub-coleções

  • Compara-se o valor procurado com o elemento no centro da coleção:

  – Se for igual, encontrou;

  – Se for menor, repete a busca na sub-coleção à esquerda do centro;

  – Se for maior, repete a busca na sub-coleção à direita do centro;

  • Não funciona sobre coleções não-ordenadas!

  • Ordem de Complexidade: O(log2 n)

  • No pior caso são realizadas “log2 n” comparações

  Busca Sequencial

  •Caminha de um por um procurando o valor

  • Mais lenta quanto maior for a coleção

  • Pode ser realizada também em estruturas não ordenadas

  • Simples

  • Ordem de Complexidade: O(n)

  • No pior caso, são realizadas “n” comparações

• Força Guerreiro!!!!!!