|
Titlul: BinarySearch Scris de: Vene Tian din Februarie 16, 2008, 19:21:04 Salut...
Am citit câteva articole de prin infoarena şi m-am lovit de următoarea funcţie: Cod: int N, A[N]; .. Nu ştiu cum să o implementez, mă poate ajuta cineva? Un mic program care caută într-un vector cu aceasta functie. Vă mulţumesc! Titlul: Răspuns: BinarySearch Scris de: HighScore din Februarie 16, 2008, 19:32:17 #-o Aia este implementarea. ???
Titlul: Răspuns: BinarySearch Scris de: Vene Tian din Februarie 16, 2008, 19:36:40 mă refeream la un exemplu.. nu prea inţeleg cum funcţionează
Titlul: Răspuns: BinarySearch Scris de: Tataranu Vlad din Februarie 16, 2008, 23:28:51 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. :wink:
Titlul: Răspuns: BinarySearch Scris de: Vene Tian din Februarie 18, 2008, 14:25:53 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 :/ Titlul: Răspuns: BinarySearch Scris de: HighScore din Februarie 18, 2008, 23:12:57 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 Titlul: Răspuns: BinarySearch Scris de: Cristian Strat din Februarie 19, 2008, 14:41:13 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.
Titlul: Răspuns: BinarySearch Scris de: Vene Tian din Februarie 22, 2008, 18:08:44 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 Titlul: Răspuns: BinarySearch Scris de: Cosmin Negruseri din Februarie 27, 2008, 21:28:34 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! |