Questão 163984

• Banca: FCC
• Órgão: TJ-PI
• Ano: 2009
• Provas: FCC - 2009 - TJ-PI - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca; Estrutura de Dados; Vetores

É um método de pesquisa ou busca, cujo algoritmo parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca, comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. Trata-se do método denominado busca

• A. por contagem.
• B. randômica.
• C. linear.
• D. binária.
• E. por comparação.

Gabarito: D

Comentários

• d-

  a busca binaria é umk algoritmo para encontrar um elemento em um array ORDENADO, baseado no esquema divide and conquer. sua complexidade em big o notation é [log2(n+1)] = [log2(n)+1]

• Busca binária

  É o método que realiza a busca por um elemento, dividindo um vetor ordenado em duas partes e testando em qual delas o elemento deveria estar, procedendo da mesma forma para a parte provável, e assim, sucessivamente, até que o elemento seja encontrado. A utilização da busca binária diminui a complexidade da busca, mas não a da inserção ou da remoção.

  Complexidade:

  - Pior caso: O(log n)

  - Caso médio: O(log n)

  - Melhor caso: 1

  Alternativa: D