Questão nº 50

Questão de Tecnologia da Informação · CESGRANRIO BASA 01/2021 (nº 50)

CESGRANRIO2021Técnico Científico - Área de Formação: Tecnologia da InformaçãoTecnologia da Informação

A classe Java a seguir contém dois métodos (busca e buscaBin) que implementam um algoritmo de busca binária sobre um array de inteiros.

public class Main {

    public static void main(String[] args) {
        int arry[]= {220,158,133,100,98,96,80,60,55,22,8};
        busca(arry,61);
    }
    public static int busca(int vet[], int elem) {
        return buscaBin(vet,elem,0,vet.length-1);
    }
    private static int buscaBin(int vet[], int elem, int ini, int fin) {
        if(ini > fin)
            return -1;
        int m=(ini+fin)/2;
        System.out.printf("%d " ,vet[m]);
        if(vet[m]==elem)
            return m;
        else
            if(vet[m]>elem)
                return buscaBin(vet,elem,m+1,fin);
            else
                return buscaBin(vet,elem,ini,m-1);
    }
}

O que será exibido no console quando o método main() for executado?

A96 80 60
B96 133 220
C96 55 60 80
D96 55 80 60 (alternativa correta)
E96 133 158 220

Resposta comentada

Gabarito Alternativa D

Conceito-chave: A busca binária divide o vetor ao meio a cada passo. Como o vetor está decrescente (220, 158, ...), a lógica de comparação (vet[m] > elem) está invertida em relação a um vetor crescente: quando o elemento do meio é maior que o procurado, a busca vai para a direita (índices maiores), e quando é menor, vai para a esquerda.

(A) Incorreta: A sequência 96 80 60 pula o passo intermediário 55, que seria visitado antes de 80 e 60, pois a busca vai para a esquerda após 96 (pois 96 > 61), e o meio da esquerda (índices 0 a 5) é o 55.
(B) Incorreta: 96 133 220 seria o caminho se o vetor fosse crescente e o elemento procurado fosse maior que todos, mas aqui o vetor é decrescente e o alvo (61) é menor que 96, então a busca vai para a esquerda, não para a direita.
(C) Incorreta: A ordem 96 55 60 80 está errada porque, após 55 (que é menor que 61), a busca vai para a direita do subvetor esquerdo (índices 3 a 5), cujo meio é o índice 4 (valor 80), e não 60.
(D) Correta: O vetor decrescente tem 11 elementos. Primeiro m=5 → vet[5]=96 (96 > 61, vai para a direita, ini=6). Depois m=8 → vet[8]=55 (55 < 61, vai para a esquerda, fin=7). Depois m=6 → vet[6]=80 (80 > 61, vai para a direita, ini=7). Por fim m=7 → vet[7]=60 (60 < 61, mas ini=8 > fin=7, retorna -1). Sequência impressa: 96 55 80 60.
(E) Incorreta: 96 133 158 220 seria o caminho se o vetor fosse crescente e o alvo fosse maior que todos, mas o vetor é decrescente e o alvo (61) é menor que 96, então a busca nunca vai para a direita após o primeiro passo.

Armadilha da banca (distrator B, o mais tentador): Muitos alunos assumem que a busca binária sempre compara com um vetor crescente. Como o vetor está decrescente, a condição vet[m] > elem faz a busca ir para a direita (índices maiores), e não para a esquerda. Quem não percebe isso inverte o caminho e escolhe a alternativa B, que mostra os elementos da direita (96 → 133 → 220), mas o alvo 61 está na metade esquerda do vetor original.

Fonte: CESGRANRIO BASA 01/2021 Técnico Científico - Área de Formação: Tecnologia da Informação. Reproduzida para fins de estudo.

Questão de Tecnologia da Informação · CESGRANRIO BASA 01/2021 (nº 50)

Resposta comentada

Continue estudando