Questão nº 63
Questão de Tecnologia da Informação · CESGRANRIO BB 01/2022 (nº 63)
Para entender como o algoritmo de busca binária se comporta, um estudante de computação resolveu inserir um comando `System.out.printf()` em um método chamado `busca`. Esse método, escrito em Java, realiza uma busca binária em um array de números inteiros, ordenados de forma ascendente. O objetivo do `printf` é exibir, no console, o valor de cada elemento do array visitado pelo algoritmo de busca binária.
Para testar o código que criou, o estudante escreveu o método main a seguir.
```java
public class Main {
public static void main(String[] args) {
int lista[]={5,18,27,33,44,49,54,67,69,72,79,86,87,92};
// o array lista possui 14 elementos
busca(78, lista);
}
public static int busca(int val,int lista[]) {
// código relativo ao algoritmo de busca binária
}
}
```
O que será exibido no console quando o método main for executado?
- A`54 79 69 72` (alternativa correta)
- B`49 72 86 79`
- C`54 86 69 72 79`
- D`67 86 72 79`
- E`54 79 67 69 72`
Resposta comentada
Gabarito Alternativa A
Busca binária funciona assim: a cada passo, você compara o valor procurado com o elemento do meio do intervalo; se o valor for menor, descarta a metade direita; se for maior, descarta a esquerda. O printf imprime cada elemento do meio visitado.
- (A) Correta: O array tem 14 elementos (índices 0 a 13). Primeiro meio = índice 6 →
54(78 > 54, vai para direita). Novo intervalo índices 7–13, meio = índice 10 →79(78 < 79, vai para esquerda). Novo intervalo índices 7–9, meio = índice 8 →69(78 > 69, vai para direita). Novo intervalo índices 9–9, meio = índice 9 →72(78 > 72, mas intervalo acaba). Sequência:54 79 69 72. - (B) Incorreta: Começa com
49(índice 5), mas o primeiro meio de um array de 14 elementos é o índice 6 (54), não o 5. A pegadinha é confundir o cálculo do meio com(início + fim) / 2arredondando para baixo, mas o índice 6 é o correto. - (C) Incorreta: Inclui
86(índice 11), que nunca é visitado porque após79o intervalo se restringe aos índices 7–9, nunca chegando ao índice 11. A armadilha é achar que o algoritmo sempre vai para o extremo direito antes de voltar. - (D) Incorreta: Começa com
67(índice 7), mas o primeiro meio é54(índice 6). A pegadinha é achar que o meio é o elemento central do array inteiro (índice 7), mas com 14 elementos, o meio é o índice 6 (arredondando para baixo). - (E) Incorreta: A sequência
54 79 67 69 72inclui67(índice 7) após79, mas após79o intervalo é índices 7–9, cujo meio é69(índice 8), não67. A armadilha é achar que o algoritmo visita todos os elementos entre os extremos, mas ele só visita os meios de cada subintervalo.
Fonte: CESGRANRIO BB 01/2022 Escriturário - Agente de Tecnologia (Caderno Gabarito 1). Reproduzida para fins de estudo.