Questão 4 da Prova 2

Questão 4 da Prova 2

por José Coelho de Pina -
Número de respostas: 2

Questão 4.

Um vetor v[0..n-1] de inteiros é dito semi-compacto se v[i+1] - v[i] ≤ 1 para i=0,...,n-2.

Escreva uma função de protótipo

     int busca(int v[], int n, int x);

que recebe um vetor semi-compacto v[0..n-1] e um inteiro x tais que v[0] ≤ x ≤ v[n-1] e retorna um índice i em [0..n-1] tal que v[i]==x.
O consumo de tempo de sua função deve ser O(lg n).

Explique sucintamente porque a sua função está correta.

Uma solução.

int 
busca(int v[], int n, int x)
{
    int e, m, d;
    e = 0;  d = n-1;
    while (/*1*/ v[e] < x && x < v[d])
    {
        m = (e + d) / 2; /* m = e + (d - e)/2;  */
        if (v[m] < x)
        {
            e = m + 1;
        }
        else
        {
            d = m;
        }
    }

    return v[e] == x? e: d;
}

Justificativa sucinta. Em /*1*/ vale que:

    (i0) 0 ≤ e ≤ d ≤ n-1, 
    (i1) v[e] ≤ x ≤ v[d].

Devido a estas relações invariantes e a condição do while, é evidente que se a função não "entra em loop" então ela retorna um índice i em [0..n-1] tal que v[i] == i. (Bem, é fácil ver que não entra em loop pois o valor de d-e decresce a cada iteração.)

Demonstração de (i0).
A invariante (i0) vale no início da primeira iteração.
Considere o início de uma iteração em que v[e] < x < v[d].
Temos que o valor de m calculado na iteração é tal que

e ≤ m < d.

(Hmmm, alguém me explica esse "e < d''? Não é possível que tenhamos m==d.)
Logo, da maneira que e ou d é alterado, vê-se que (i0) vale no início da próxima iteração.

Demonstração de (i1).
A invariante (i1) vale no início da primeira iteração, já que supomos que v[0] ≤ x ≤ v[n-1].
Considere o início de uma iteração em que v[e] < x < v[d].
Se a atribuição "e = m + 1;" é executada, então tem-se que

(1)    v[m+1] ≤ v[m] + 1 ≤ x - 1 + 1 = x,

onde o primeiro ''≤'' vale pois v é semi-compacto (Ufa! tinha que usar isto em algum lugar!).
Se a atribuição "d = m;" é executada, então vale que

(2)    x ≤ v[m].

De (1) e (2) concluí-se que (i1) vale no início da próxima iteração.

Em resposta à José Coelho de Pina

Re: Questão 4 da Prova 2

por José Coelho de Pina -

Salve,

A seguir está uma versão recursiva de solução inspirada na primera solução neste tópico.

int 
busca(int v[], int n, int x)
{
    return buscaR(v, 0, n-1, x);
}

int
buscaR(int v[], int e, int d, int x)
{
    int m;

    if (v[m = (e+d)/2] == x) return m;
    if (v[m] < x) return buscaR(v, m+1, d, x);
    return buscaR(v, e, m-1, x); 		      

}
Em resposta à José Coelho de Pina

Re: Questão 4 da Prova 2

por José Coelho de Pina -

A seguir estão duas soluções que exploram de uma maneira mais evidente que o vetor dado é semi-compacto.
A primeira e iterativa e a segunda é a correspondente versão recursiva inspirada na primeira.

int 
busca(int v[], int n, int x)
{
    int e, m, d;
    e = 0;  d = n-1;
    while (v[e] < x && x < v[d])
    {
        m = (e + d) / 2; /* m = e + (d - e) / 2; */
        if (v[m] < x)
        {
            e = m + x - v[m]; /* x - v[m] >= 1 */
        }
        else
        {
            d = m + x - v[m]; /* x - v[m] <= 0 */
        }
    }

    return v[e] == x? e: d;
}

int 
busca(int v[], int n, int x)
{
    return buscaR(v, 0, n-1, x);
}

int
buscaR(int v[], int e, int d, int x)
{
    int m;

    if (v[m = (e+d)/2] == x) return m;
    if (v[m] < x) return buscaR(v, m+x-v[m], d, x); /* x - v[m] >= 1 */
    return buscaR(v, e, m+x-v[m], x); 	/* x - v[m] <= -1 */	      

}