Cautare Binara

[•MciprianM]

Am gasit recent o cautare binara care arata foarte interesant:

Cod:

int bsearch (int a [], int n, int x) { //cauta pe x in a [0 .0. n - 1]
    int i, base = 0, index;
    for (i = n; i != 0; i >>= 1) {
        index = base + (i >> 1);
        if (a [index] == x)
            return index;
        if (a [index] < x) {
            base = index + 1;
            -- i;
        }
    }
    return -1;
}

Nu am inteles chiar bine de ce functioneaza (si daca functioneaza). Ce ziceti? Seamana cu cautarea binara de la smenuri de programare.

[•wefgef]

Face exact acelasi lucru ca si cautarea binara din articolul mentionat de tine. Pe aceea esti sigur ca ai inteles-o?

[•MciprianM]

In articolul mentionat mai sus, variabila pas contine puteri ale lui 2. Astfel putem obtine orice indice din sirul dat.
Acuma ca m-am mai gandit la cautarea asta, in cazul de fata, variabila i ia ca valori dimensiunea spatiului de cautare. Asa ca eu cred ca aduce mai degraba cu cautarea clasica.