SóProvas

ID
1567024
Banca
COSEAC
Órgão
UFF
Ano
2015
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere o seguinte vetor:


[45, 58, 86, 104, 134, 250, 315, 367, 408, 410, 502, 510, 600, 785, 846, 901]


Utilizando-se uma pesquisa binária, o número máximo de buscas para encontrar a chave 600 será: 

Alternativas
Comentários

  • A pesquisa binária funciona da seguinte forma:

    Divide-se o vetor ao meio (ex: 16/2 = 8) 

    Verifica se o elemento central é igual ao item procurado, se sim a busca finaliza, se não verifica se o item é maior ou menor que o elemento central do vetor.

    Se for menor: elimina-se toda a parte direita do elemento central (incluíndo este) (uma vez que a pesquisa binária trabalha com elementos ordenados) - Repete-se o processo de comparação.

    Se for maior: elimina-se toda a parte esquerda do elemento central...Repete-se o processo de comparação.

  • Ordenação binária de vetores

     

    Utilizando-se uma pesquisa binária, o número máximo de buscas para encontrar a chave 600 será:

    [45, 58, 86, 104, 134, 250, 315, 367, 408, 410, 502, 510, 600, 785, 846, 901]

    Resolução:

    1°Busca

    Inicial do vetor:1 posição

    Meio do vetor:8 posição

    Final do vetor:16 posição

    Obs:Para achar o meio do vetor devemos dividir o número final da posição pela a posição inicial, assim achar um valor exato na divisão e dar prosseguimento na busca.Ex.(16+1)/2=8 posicão.

    Feito isso verificasse se o conteúdo do vetor da 8 posição é maior ou menor que valor que deseja encontrar(600).Se for menor eliminasse todas as posições do lado

    [45, 58, 86, 104, 134, 250, 315, 367, 408, 410, 502, 510, 600, 785, 846, 901]

    esquerdo do numero do meio;

    2°Busca

    Inicial do vetor:9 posição

    Meio do vetor:12 posição

    Final do vetor:16 posição

    Meio do vetor:(16+9)/2=12

     

    [45, 58, 86, 104, 134, 250, 315, 367, 408, 410, 502, 510, 600, 785, 846, 901]

    3°Busca

    Inicial do vetor:13 posição

    Meio do vetor: 14posição

    Final do vetor:16 posição

    Meio do vetor:(16+13)/2=14

    Agora verificasse se o valor do Meio do vetor é maior ou menor que o numero desejado. Assim o numero localizado na 14 posição é 785 que é maior que 600.Com isso eliminasse todos os vetores da direita do numero.

    [45, 58, 86, 104, 134, 250, 315, 367, 408, 410, 502, 510, 600, 785, 846, 901]

     

    4°Busca

    O ultimo numero que resta é o da posição 13 que é justamente o valor preocurado.

  • Para ganhar tempo na prova:

    Busca binária -> x = Log N na base 2.

    N = 16, então 2^X = 16

    X = 4

    esqueça o 600, isso foi só para te fazer perder tempo.

  • Força Guerreiro!!!!!!