Questão FC373182
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
Algoritmos e Lógica de Programação
FCC · 2022
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) {
\(\overset{I}{......}\);
if (x == vetor[m]) {
System.out.println("O valor " + x + " foi encontrado");
return;
}
if (x < vetor[m]) {
\(\overset{II}{......}\);
} else {
\(\overset{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
- m = (i − f) / 2 m = f − 1 m = i + 1
- m = (i + f) / 2 f = m – 1 i = m + 1
- m = (i + f) * 2 f = m + 1 i = m − 1
- m = (i + f) / 2 f = m + 1 i = m − 1
- m = (i − f) / 2 f = m − 1 i = m + 1
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
A lacuna ΔI é preenchida por \(m = \tfrac{i + f}{2}\). Esse cálculo escolhe o índice do meio do intervalo atual, ponto central da busca binária, evitando varredura linear.
Quando \(x == vetor[m]\) o elemento foi encontrado e o método retorna. Se \(x < vetor[m]\) deve-se reduzir o limite superior do intervalo: atribui‑se \(f = m - 1\), eliminando a metade direita (incluindo m) da busca.
Se \(x > vetor[m]\) avança‑se o limite inferior: atribui‑se \(i = m + 1\), eliminando a metade esquerda (incluindo m).
Esses ajustes mantêm a invariante de que o elemento procurado, se existir, está sempre entre \(i\) e \(f\), e garantem que o intervalo diminui a cada iteração até \(i>f\), quando se conclui que o valor não existe no vetor.
Por fim, a estratégia provê ordenação das verificações e convergência rápida, caracterizando complexidade O(log n).
Conteúdo do catálogo FC Concursos · Atualizado em