Algoritmos e Estrutura de Dados · IV - UFG · 2023 | Questão sqc-qq862236

Algoritmos e Estrutura de DadosAlgoritmos

Código: qq862236
Banca: IV - UFG
Órgão: Prefeitura de Morrinhos - GO
Ano: 2023
Nível: Médio

Cargo: CS-UFG - - Técnico em Suporte de Tecnologia da Informação

Para a busca de um determinado valor em um vetor de elementos numéricos, como funciona o algoritmo de busca binária?

AO algoritmo converte os elementos do vetor para a representação binária, realiza uma comparação bit a bit para determinar se o padrão binário correspondente ao valor buscado existe ou não no vetor e, em caso positivo, realiza uma varredura para determinar a posição ocupada no vetor pelo elemento com o valor buscado.
BO algoritmo opera tanto em vetores ordenados quanto em não ordenados, por meio da comparação do valor buscado com o elemento central do vetor, para determinar se a busca prosseguirá na metade da esquerda ou na metade da direita do vetor, até que todas as ocorrências do valor buscado sejam encontradas.
CO algoritmo realiza uma varredura do vetor, comparando cada um de seus elementos com o valor buscado e anotando, em um mapa de bits auxiliar, todas as posições do vetor em que o valor buscado foi encontrado; o mapa de bits é retornado como resultado da execução do algoritmo.
DO algoritmo opera em vetores ordenados e funciona por meio da comparação do valor buscado com o valor do elemento central do vetor para determinar se a busca prosseguirá, recursivamente, na metade da esquerda ou na metade da direita do vetor, até que o valor buscado seja encontrado ou até que se descubra que o valor buscado não existe no vetor.

Revelar gabarito e comentário

GabaritoD — O algoritmo opera em vetores ordenados e funciona por meio da comparação do valor buscado com o valor do elemento central do vetor para determinar se a busca prosseguirá, recursivamente, na metade da esquerda ou na metade da direita do vetor, até que o valor buscado seja encontrado ou até que se descubra que o valor buscado não existe no vetor.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Algoritmo de Busca Binária

Gabarito: alternativa D. A busca binária requer que o vetor esteja ordenado e funciona dividindo repetidamente o intervalo de busca ao meio, comparando o valor central com o alvo, e recursivamente buscando na metade esquerda ou direita até encontrar ou esgotar o espaço de busca.

A banca testa o entendimento conceitual do algoritmo, incluindo seus pré-requisitos (vetor ordenado) e seu comportamento (busca recursiva, parada quando encontrado ou não existe).

Alternativa A — ❌ Incorreta

Descreve um algoritmo que converte números para binário e compara bits. Isso não é busca binária; é uma confusão com o termo "binária" (base 2). A busca binária recebe esse nome por dividir o espaço de busca em duas partes a cada iteração, não por usar representação binária.

Alternativa B — ❌ Incorreta

Afirma que opera tanto em vetores ordenados quanto não ordenados. A busca binária exige que o vetor esteja ordenado, pois a decisão de ir para a esquerda ou direita baseia-se na comparação com o elemento central. Além disso, a descrição diz "até que todas as ocorrências sejam encontradas", o que não é o comportamento padrão: a busca binária clássica para ao encontrar a primeira ocorrência ou ao determinar a ausência.

Alternativa C — ❌ Incorreta

Descreve uma varredura linear com mapa de bits. Isso é uma busca sequencial, não binária. A busca binária não percorre o vetor inteiro; ela salta para o meio e reduz o intervalo.

Alternativa D — ✅ Correta ⟵ GABARITO

Corretamente descreve a busca binária: requer vetor ordenado, compara com o elemento central, e prossegue recursivamente na metade esquerda ou direita até encontrar o valor ou descobrir que não existe. Essa é a definição clássica do algoritmo, com complexidade O(log n).

PEGA ESSA DICA!

Lembre-se: o pré-requisito fundamental da busca binária é a ordenação do vetor. Sem ordenação, o algoritmo não funciona. Para fixar, compare com a busca sequencial (linear), que não exige ordenação, mas tem complexidade O(n).

Gabarito: letra D.

Link permanente: /questoes/qq862236