Questão FC373273
Considere a classe Java abaixo. public class Procura { public static void main(String[] args) { int k[] = {8, 44, 45, 70, 72, 95}; int n = k.length; int x = 70; System.out.print(bu
Linguagens de Programação
FCC · 2019
Considere a classe Java abaixo.
public class Procura {
public static void main(String[] args) {
int k[] = {8, 44, 45, 70, 72, 95};
int n = k.length;
int x = 70;
System.out.print(busca ..I..);
}
static int busca(int a, int b, int v[]) {
int e = -1, d = b;
while (e < d - 1) {
int t = (e + d) / 2;
if (..II.. ) {
e = t;
} else {
d = t;
}
}
return d;
}
}
Para que esta classe mostre a posição (índica) do vetor onde se encontra o valor 70, as lacunas I e II devem ser corretamente preenchidas por
- (x, n, k) e v[t] <= a
- (x, n, k[]) e v[t] < a
- (x, n, k) e v[t] < a
- (a, b, v) e v[t] < a
- (a, b, v) e v[t] = a
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
Chamar busca(x, n, k) corresponde exatamente à assinatura do método: o primeiro parâmetro (a) é o valor procurado (x), o segundo (b) é o limite direito do intervalo (o comprimento n do vetor) e o terceiro é o próprio vetor (k).
No laço, as variáveis de controle são e = -1 e d = b. A cada iteração calcula-se \(t = (e + d) / 2\) e testa-se a condição sobre v[t].
Usar v[t] < a faz com que, quando o elemento no meio for estritamente menor que o alvo, avance-se a borda esquerda (e = t); caso contrário (incluindo igualdade) reduz-se a borda direita (d = t).
Ao terminar o while (condição \(e < d - 1\)), a função retorna d, que passa a ser o índice da primeira posição cujo valor é maior ou igual a a. No vetor dado isso resulta em 3, posição onde está 70.
Conteúdo do catálogo FC Concursos · Atualizado em