Fórum de discussão

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 */	      

}