2 (1 pt). Suponha que você tenha a vetor ordenado
e que você esteja usando o algoritmo recursivo da busca binária. Qual grupo de números mostra corretamente a sequência de comparações usadas para encontrar a chave 15 ? Ou seja, os valores que serão impressos nessa versão modificada
int buscaBinaria (int x, int n, int v[]) (
int e = -1, d = n;
while (e < d-1) {
int m = (e + d)/2;
printf ("%d\n", v[m]);
if (v[m] < x) e = m; else d = m;
}
return d;
}
int buscaBinaria (int x, int n, int v[]) (
int e = -1, d = n;
while (e < d-1) {
int m = (e + d)/2;
printf ("%d\n", v[m]);
if (v[m] < x) e = m; else d = m;
}
return d;
}
Passo 1
O enunciado pede: identificar a sequência de valores impressos pelo trecho de código dado quando se busca a chave
.
Informações fornecidas:
— vetor ordenado de
elementos (índices
a
).
Chave procurada: .
Código inicializa e
e, a cada iteração, calcula
(divisão inteira), imprime
e então atualiza
ou
conforme
ou não. Precisamos listar os valores de
que serão impressos, na ordem em que aparecem.
Informações fornecidas:
Chave procurada:
Código inicializa
Passo 2
Vou explicar como o algoritmo funciona, passo a passo (conceito essencial):
-
e são os limites da busca; sempre consideramos que os possíveis candidatos estão em índices maiores que e menores que . - A cada iteração escolhemos o meio com
(divisão inteira dá a parte inteira) e comparamos com a chave . - Se
então todos os índices não podem conter , logo movemos para . Caso contrário movemos para . - O laço termina quando não há espaço entre
e , ou seja quando .
Isso significa que os valores que aparecem são exatamente oscalculados em cada iteração até o laço parar. Agora vamos calcular cada iteração com calma.
Passo 3
Iteração 1 — valores iniciais:
.
Calcule o meio:
Calcule o meio:
Imprime-se
. Olhando o vetor (peguei os valores do enunciado),
.
Comparação: é verdadeira, então atualizamos
.
Comparação:
Passo 4
Iteração 2 — agora
.
Calcule o meio:
Calcule o meio:
Imprime-se
. Do vetor,
.
Comparação: é falsa, então atualizamos
.
Comparação:
Passo 5
Iteração 3 — agora
.
Calcule o meio:
Calcule o meio:
Imprime-se
. Do vetor,
.
Comparação: é verdadeira, então atualizamos
.
Comparação:
Passo 6
Iteração 4 — agora
.
Calcule o meio:
Calcule o meio:
Imprime-se
. Do vetor,
.
Comparação: é falsa (é igual), então atualizamos
.
Comparação:
Passo 7
Verificação de término: agora
. A condição do laço é
. Substituindo,
que é falsa. Portanto o laço termina. Os valores impressos, na ordem, foram aqueles calculados nas iterações anteriores.