Questão nº 32

Questão de Tecnologia da Informação · FCC TRT5 2022 (nº 32)

FCC2022Analista Judiciário - Área Apoio Especializado - Especialidade Tecnologia da InformaçãoTecnologia da Informação

Considere o método Java a seguir, que objetiva realizar uma busca binária em um vetor de inteiros ordenado de forma crescente.

public static void buscar (int x, int vetor[]) {
    int i, f, m;
    i = 0;
    f = vetor.length - 1;
    while (i <= f) {
        I ;
        if (x == vetor[m]) {
            System.out.println("O valor " + x + " foi encontrado");
            return;
        }
        if (x < vetor[m]) {
            II ;
        } else {
            III ;
        }
    }
    System.out.println("O valor " + x + " não foi encontrado");
}

Para que a busca binária execute corretamente e dê uma resposta ao usuário para qualquer valor x buscado, existente ou não no vetor, as lacunas I, II e III devem ser, correta e respectivamente, preenchidas por

Am = (i − f) / 2 / m = f − 1 / m = i + 1
Bm = (i + f) / 2 / f = m − 1 / i = m + 1 (alternativa correta)
Cm = (i + f) * 2 / f = m + 1 / i = m − 1
Dm = (i + f) / 2 / f = m + 1 / i = m − 1
Em = (i − f) / 2 / f = m − 1 / i = m + 1

Resposta comentada

Gabarito Alternativa B

A busca binária é um algoritmo eficiente para encontrar um item em uma lista ordenada (neste caso, um vetor de inteiros em ordem crescente). Ela funciona dividindo repetidamente a parte da lista onde o item pode estar pela metade, eliminando a metade que não pode conter o item.

(A) Incorreta: A fórmula para m está incorreta (i - f em vez de i + f), e as atualizações para f e i também estão incorretas ou incompletas (f = f - 1 não usa m).
(B) Correta:
- I: m = (i + f) / 2 calcula o índice do meio da sub-lista atual, que é o ponto central para a divisão.
- II: Se x < vetor[m], significa que o valor procurado x deve estar na metade esquerda do vetor. Assim, o novo limite final f deve ser m - 1, excluindo m e tudo à direita.
- III: Se x > vetor[m] (pois x == vetor[m] já foi tratado), significa que x deve estar na metade direita. O novo limite inicial i deve ser m + 1, excluindo m e tudo à esquerda.
(C) Incorreta: A fórmula para m está incorreta (* 2 em vez de / 2), e as atualizações para f e i estão invertidas ou incorretas.
(D) Incorreta: Embora m = (i + f) / 2 esteja correto, as atualizações para f e i estão incorretas. Se x < vetor[m], o novo limite final f deve ser m - 1 (para buscar na metade esquerda), não m + 1. Se x > vetor[m], o novo limite inicial i deve ser m + 1 (para buscar na metade direita), não m - 1. Armadilha: Esta alternativa é tentadora porque a primeira parte (m = (i + f) / 2) está correta, mas as atualizações subsequentes para os limites f e i estão trocadas ou incorretas, o que faria o algoritmo falhar ou entrar em loop infinito.
(E) Incorreta: A fórmula para m está incorreta (i - f em vez de i + f).

Fonte: FCC TRT5 2022 Analista Judiciário - Área Apoio Especializado - Especialidade Tecnologia da Informação (Caderno Tipo 001). Reproduzida para fins de estudo.

Questão de Tecnologia da Informação · FCC TRT5 2022 (nº 32)

Resposta comentada

Continue estudando