BinarySearch

[•Sycron]

Salut...
Am citit câteva articole de prin infoarena şi m-am lovit de următoarea funcţie:

Cod:

int N, A[N];   
  
int binary_search(int val)   
{   
    int i, step;   
    for (step = 1; step < N; step <<= 1);   
    for (i = 0; step; step >>= 1)   
        if (i + step < N && A[i + step] <= val)   
           i += step;   
    return i;   
}  

.. Nu ştiu cum să o implementez, mă poate ajuta cineva?
Un mic program care caută într-un vector cu aceasta functie.
Vă mulţumesc!

[•skyel]

Aia este implementarea.

[•Sycron]

mă refeream la un exemplu.. nu prea inţeleg cum funcţionează

[•tvlad]

Pozitiile se impart in 2 parti dupa cel mai semnificativ bit. Determini unde este valoarea cautata de tine si setezi sau nu bitul respectiv. Dupa aia treci la urmatorul bit, care imparte intervalul mai mic pe care l-ai ales.

[•Sycron]

Cod:

int N, A[N]; 

am impresia ca acesta bucata de cod face ca functia sa nu mai fie generala...
adica:

cauta(vector,lungime_vector,valoare_cautata); //(mi se pare a fi mai generala)

daca pun

Cod:

int N, A[N]; 

va fi valabila pentru vectorul A de lungime N, NU??


P.S. Din functia asta, nu am inteles bucata de cod de mai sus... cine ma poate lamuri ii dau o ciocolata :/

[•skyel]

Tu realizezi ca persoanele care au scris articolul au dat un simplu exemplu de cautare binara(by Mihai Patrascu). In alte cuvinte au avut si altceva mai bun de facut decat sa scrie toate modurile in care poti scrie functia.

P.S. Daca analizezi putin observi ca frumusetea cautarii respective binare e ca nu are nevoie de functii, evitand timpul pierdut prin apeluri.

P.P.S. Nimeni nu a vrut ca functia respectiva sa fie "mai generala".

P.P.P.S. Si ca sa iti raspund si la intrebare bucata respectiva de cod este folosita pentru a declara un vector si o variabila. Vectorul este notat simbolic A[N], cat despre a intelege sau nu, cred ca de fapt compilatorul nu a inteles. Dar dehh se mai intampla chestii d-astea la copy+paste

[•wickedman]

Daca nu iti este evident cum functioneaza functia asta mai bine folosesti implementarea "obisnuita" a algoritmului de cautare binara.  Este mult mai usor de inteles si merge la fel de repede.

[•Sycron]

pentru ONI cred ca este de ajuns cautarea binara standard.

o să încerc să înţeleg funcţia lui Mihai Pătraşcu , dar mai am de studiat până atunci

[•Cosmin]

Eu tot busheam implementarea la cautare binara, si dupa o perioada am aflat ca e o problema generala nu doar a mea. O gramada de oameni bushesc la implementarea cautarii binare.
Daca implementezi cu invarianti in minte atunci practic demonstrezi si corectitudinea algoritmului.
Citeste articolul asta si nu vei mai avea probleme cu implementarea unei cautari binare: http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary
Nu vei mai bushi daca sunt mai multe elemente egale cu cel cautat, sau daca sirul e prea mic sau daca elementul cautat nu exista sau mai stiu eu ce alte cazuri crezi ca pot aparea.

Mai ai aici un algoritm bun de cautare binara: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Metoda lui Mihai e doar una interesanta ca si cod dar mai bine inveti sa scrii simplu si corect decat sa inveti ceva mai complicat .

Bafta!