2 (1 pt). Suponha que você tenha a vetor ordenado \{3,5,6,8,11,12,14,15,17,18,22\} 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;
}

Passo 1

O enunciado pede: identificar a sequência de valores impressos pelo trecho de código dado quando se busca a chave \,15.
Informações fornecidas:
\{3,5,6,8,11,12,14,15,17,18,22\} — vetor ordenado de n=11 elementos (índices 0 a 10).
Chave procurada: x=15.
Código inicializa \,e=-1 e \,d=n=11 e, a cada iteração, calcula \,m=(e+d)/2 (divisão inteira), imprime \,v[m] e então atualiza \,e ou \,d conforme \,v[m]<x ou não. Precisamos listar os valores de \,v[m] que serão impressos, na ordem em que aparecem.

Passo 2

Vou explicar como o algoritmo funciona, passo a passo (conceito essencial):
  • e e d são os limites da busca; sempre consideramos que os possíveis candidatos estão em índices maiores que e e menores que d.
  • A cada iteração escolhemos o meio com \,m=\lfloor (e+d)/2\rfloor (divisão inteira dá a parte inteira) e comparamos \,v[m] com a chave x.
  • Se \,v[m]<x então todos os índices \le m não podem conter x, logo movemos e para m. Caso contrário movemos d para m.
  • O laço termina quando não há espaço entre e e d, ou seja quando e\ge d-1.
    Isso significa que os valores que aparecem são exatamente os \,v[m] calculados em cada iteração até o laço parar. Agora vamos calcular cada iteração com calma.

Passo 3

Iteração 1 — valores iniciais: \,e=-1,\\ d=11.
Calcule o meio:
m=\left\lfloor\frac{e+d}{2}\right\rfloor=\left\lfloor\frac{-1+11}{2}\right\rfloor=\left\lfloor\frac{10}{2}\right\rfloor=5.
Imprime-se \,v[5]. Olhando o vetor (peguei os valores do enunciado), \,v[5]=12.
Comparação: \,12<15 é verdadeira, então atualizamos \,e=5.

Passo 4

Iteração 2 — agora \,e=5,\\ d=11.
Calcule o meio:
m=\left\lfloor\frac{5+11}{2}\right\rfloor=\left\lfloor\frac{16}{2}\right\rfloor=8.
Imprime-se \,v[8]. Do vetor, \,v[8]=17.
Comparação: \,17<15 é falsa, então atualizamos \,d=8.

Passo 5

Iteração 3 — agora \,e=5,\\ d=8.
Calcule o meio:
m=\left\lfloor\frac{5+8}{2}\right\rfloor=\left\lfloor\frac{13}{2}\right\rfloor=6.
Imprime-se \,v[6]. Do vetor, \,v[6]=14.
Comparação: \,14<15 é verdadeira, então atualizamos \,e=6.

Passo 6

Iteração 4 — agora \,e=6,\\ d=8.
Calcule o meio:
m=\left\lfloor\frac{6+8}{2}\right\rfloor=\left\lfloor\frac{14}{2}\right\rfloor=7.
Imprime-se \,v[7]. Do vetor, \,v[7]=15.
Comparação: \,15<15 é falsa (é igual), então atualizamos \,d=7.

Passo 7

Verificação de término: agora \,e=6,\\ d=7. A condição do laço é \,e<d-1. Substituindo,
6<7-1 \quad\text{é}\quad 6<6,é
que é falsa. Portanto o laço termina. Os valores impressos, na ordem, foram aqueles calculados nas iterações anteriores.

Resposta

\{12,\,17,\,14,\,15\}

Exercícios relacionados