infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: MciprianM din Octombrie 02, 2011, 21:40:20

Titlul: Cautare Binara
Scris de: MciprianM din Octombrie 02, 2011, 21:40:20

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.

Titlul: Răspuns: Cautare Binara
Scris de: Andrei Grigorean din Octombrie 04, 2011, 22:21:50

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

Titlul: Răspuns: Cautare Binara
Scris de: MciprianM din Octombrie 04, 2011, 22:46:22

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.