SóProvas

ID
2409274
Banca
FUNDEP (Gestão de Concursos)
Órgão
UFVJM-MG
Ano
2017
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Analise o trecho de código a seguir.
Avariável x representa o elemento de referência passado como parâmetro
while( inicio <= termino )
{
meio = ( inicio + termino ) / 2;
if( a[ meio ].compareTo( x ) < 0 )
inicio = meio + 1;
else if( a[ meio ].compareTo( x ) > 0 )
termino = meio - 1;
else
return meio;
}
A qual algoritmo esse código pertence?

Alternativas
Comentários

  • O gabarito é a letra A. 

     

    A pesquisa ou busca binária é 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.

  • Uma das maiores diferenças para o "quick-sort", item (D) (da árvore binária, item (A) e do "heap-sort", item (B)) é que neste algoritmo um elemento qualquer é escolhido (geralmente aleatório) para ser o "pivot". Assim, à esquerda desse "pivot" os elementos menores são ordenados inicialmente, depois elege-se um novo "pivot" para a outro lado (o direito), ordenando-se esta segunda parte os elementos.

    Podem ser eleitos vários "pivots" durante a ordenação.

    A árvore binária sempre procura dividir os elementos a serem ordenados em dois grupos, partindo da metade dos elementos a serem ordenados, assim, sucessivamente, até restar dois, é parecido, nesta etapa (somente) com o "merge-sort", contudo as estruturas, "árvore-binária" X merge-sort são bem distintas, a primeira ("árvore-binária") não é uma estrutura linear, já a segunda ("merge-sort") é.

    Já a "heap-sort" (é muito parecida com as árvores) diferencia-se da árvore por colocar os elementos maiores (caso seja ordenação crescente) no final do vetor, e, além disso, numa etapa anterior o algoritmo heap-sort ordena de forma decrescente a árvore (meio confuso mas é eficiente), para, só na etapa final ordenar de forma decrescente (caso seja para ordenar neste sentido).

  • Força Guerreiro!!!!!!