Questão nº 35
Questão de Engenharia de Software, DevOps e Ciência de Dados · FCC MPEPE 2018 (nº 35)
Considere o método Java abaixo.
```
int verifica(int x, int n, int v[]) {
int e = -1, d = n;
while (e < d - 1) {
int m = (e + d) / 2;
if (v[m] < x) {
e = m;
} else {
d = m;
}
}
return d;
}
```
O método verifica recebe os valores abaixo para x, n e v[].
```
x = 98
n = 6
v[] = {10, 23, 45, 78, 98, 125}
```
Conclui-se corretamente que
- Aocorrerá um erro na linha que contém o comando `while (e < d - 1) {`.
- Bocorrerá uma exceção do tipo `ArrayIndexOutOfBoundsException`.
- Co retorno do método será 4. (alternativa correta)
- Docorrerá um erro na linha que contém o comando `if (v[m] < x) {`.
- Eo retorno do método será 1.
Resposta comentada
Gabarito Alternativa C
O método implementa uma variação da busca binária, um algoritmo eficiente para encontrar a posição de um elemento em um array ordenado. Ele funciona dividindo repetidamente o intervalo de busca ao meio, eliminando metade dos elementos a cada passo, até encontrar o ponto de inserção ou o primeiro elemento maior ou igual ao valor procurado.
Vamos rastrear a execução com os valores fornecidos:
x = 98
n = 6
v[] = {10, 23, 45, 78, 98, 125}
Estado inicial: e = -1, d = 6
-
Loop 1:
while (e < d - 1):(-1 < 6 - 1)->(-1 < 5)é verdadeiro.m = (e + d) / 2:(-1 + 6) / 2->5 / 2->2(divisão inteira).if (v[m] < x):(v[2] < 98)->(45 < 98)é verdadeiro.e = m:etorna-se2.- Estado:
e = 2,d = 6.
-
Loop 2:
while (e < d - 1):(2 < 6 - 1)->(2 < 5)é verdadeiro.m = (e + d) / 2:(2 + 6) / 2->8 / 2->4.if (v[m] < x):(v[4] < 98)->(98 < 98)é falso.else:d = m:dtorna-se4.- Estado:
e = 2,d = 4.
-
Loop 3:
while (e < d - 1):(2 < 4 - 1)->(2 < 3)é verdadeiro.m = (e + d) / 2:(2 + 4) / 2->6 / 2->3.if (v[m] < x):(v[3] < 98)->(78 < 98)é verdadeiro.e = m:etorna-se3.- Estado:
e = 3,d = 4.
-
Loop 4:
while (e < d - 1):(3 < 4 - 1)->(3 < 3)é falso. O loop termina.
-
Retorno:
return d: O método retorna o valor atual ded, que é4.
(A) Incorreta: A condição while (e < d - 1) é uma expressão booleana válida e não causa nenhum erro de sintaxe ou de tempo de execução.
(B) Incorreta: Os valores de m calculados durante a execução (2, 4, 3) estão sempre dentro dos limites válidos do array v (índices de 0 a 5). Portanto, não ocorrerá uma ArrayIndexOutOfBoundsException. A armadilha aqui é pensar que e = -1 ou d = n (que é 6) poderiam levar a um índice inválido, mas o cálculo de m e a lógica do loop garantem que m sempre será um índice válido para acesso ao array.
(C) Correta: Conforme o rastreamento detalhado acima, o método retorna o valor 4 ao final da execução. Este tipo de busca binária retorna o índice do primeiro elemento que é maior ou igual a x (ou n se x for maior que todos os elementos). No array v, o valor 98 está no índice 4.
(D) Incorreta: A condição if (v[m] < x) é uma comparação válida entre dois inteiros e não causa nenhum erro.
(E) Incorreta: O rastreamento da execução demonstra que o valor de retorno é 4, e não 1.
Fonte: FCC MPEPE 2018 Analista Ministerial - Área Informática (Caderno Tipo 1). Reproduzida para fins de estudo.