Questão 759355

• Banca: PaqTcPB
• Órgão: UEPB
• Ano: 2012
• Provas: PaqTcPB - 2012 - UEPB - Técnico em Informática - Programador
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Busca ou pesquisa binária é um algoritmo de busca em vetores ordenados. Sobre o algoritmo de busca binária é correto afirmar:

I - No pior caso tem complexidade O(log n).

II - No melhor caso tem complexidade O(log n).

III - No caso médio tem complexidade O(1).

IV - No melhor caso tem complexidade O(n).

Está(ão) correta(s)

• A. Apenas I.
• B. Apenas II e III.
• C. Apenas III e IV.
• D. Apenas II e IV.
• E. I, II, III e IV.

Gabarito: A

Comentários

• A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela 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.
  
  caso médio: 
  melhor caso: 
  pior caso: 
  
  http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria
  

• O pior caso não seria O(n)?

• complexidade caso médio : O(log n)

  complexidade melhor caso : O(1)

  complexidade de pior caso : O(log n)

• Força Guerreiro!!!!!!