Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Cautarea ta binara este gresita  (Citit de 17692 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« : Ianuarie 07, 2012, 14:59:15 »

Comentarii la postul http://infoarena.ro/blog/cautare-binara
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : Ianuarie 07, 2012, 15:21:09 »

La IOI 2007, atît eu cît și gcosmin am luat 80 de puncte pe o problemă pentru ca depășeam int-ul cînd adunam hi + lo.

Sfaturi foarte bune în acest post!
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #2 : Martie 01, 2012, 22:01:37 »

Inainte de toate, al doilea cod functioneaza pentru un sir indexat de la 1 sau de la 0?

Oricum ar fi, mie nu-mi functioneaza pe cazul in care elementul cautat se afla pe ultima pozitie in sirul sortat.
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #3 : Martie 01, 2012, 22:10:16 »

Nu sunt sigur dar cred ca,ironic, si cautarea aia binara e gresita  Very Happy
Ia vezi iti merge daca in linia zece in loc de || pui && ?
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #4 : Martie 01, 2012, 22:13:29 »

Atunci nu merge pentru cazul in care elementul cautat se afla pe prima pozitie Smile)
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #5 : Martie 01, 2012, 22:16:55 »

Mie imi merge si pentru prima pozitie. Poti pune codul aici ?
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #6 : Martie 01, 2012, 22:18:45 »

Cod:
#include <cstdio>

int N, A[1005];

int binary_search(int val)
{
    int hi=N, lo=-1, mid;
while(hi - lo > 1){
mid=lo+(hi-lo)/2;
if(A[mid] <= val)
lo=mid;
else
hi=mid;
}
if(hi==N && A[hi]!=val)
return -1;
else
return hi;
}

int main(){

freopen("date.in","r",stdin);
int j, poz, x;
scanf("%d",&N);
for(j=0; j<N; ++j)
scanf("%d",&A[j]);

scanf("%d",&x);

poz=binary_search(x);


printf("\n%d",poz);
}
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #7 : Martie 01, 2012, 22:26:23 »

Mie tot imi merge. Pentru ce set de date nu ti-a functionat tie ?
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #8 : Martie 01, 2012, 22:27:59 »

7
1 3 3 4 5 6 7
1


Pe prima linie numarul de elemente. Pe a doua elementele. Pe a treia elementul cautat
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #9 : Martie 01, 2012, 22:35:38 »

Am descoperit o greseala in codul tau. Ai indexat vectorul de la 0, deci ultimul numar se afla pe pozitia N-1. Modifica in cautare hi=N-1
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #10 : Martie 01, 2012, 22:43:48 »

neah, nu merge nici asa, imi zice ca 1 se afla pe pozitia 1, dar de fapt e pe 0. La tine merge cum trebuie? Ai sirul indexat de la 1 sau de la 0?
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #11 : Martie 01, 2012, 23:02:08 »

Ai dreptate, asa e si la mine. Nu stiu, ma depaseste. O sa las pe altcineva mai in masura sa iti raspunda.  Whistle
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #12 : Martie 01, 2012, 23:02:55 »

Ok, mersi oricum pentru efortul depus Smile
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #13 : Martie 01, 2012, 23:07:24 »

Codul din blog post e bun.

Ti-am gasit greseala, ai schimbat din a[mid] < x in a[mid] <= x.

Adica ai bushit exact unde ziceam sa fi atent in articol, la pastrarea invariantului a[lo] < x <= a[hi]. daca lo = -1 si hi = N invariantul asta e valid, deci sugestia cu hi = N-1 era gresita daca vrei sa folosesti invariantul ce l-am mentionat.

Daca tii neaparat sa testezi a[mid] <= x atunci trebuie sa folosesti alt invariant cu a[lo] <= x < a[hi] si sa retunezi ca rezultat pozitia lo daca ea nu e -1 (adica, daca elementul a fost gasit in sir).
« Ultima modificare: Martie 01, 2012, 23:14:16 de către Cosmin Negruseri » Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #14 : Martie 01, 2012, 23:25:27 »

Aoleu aoleu aoleu.
Ai dreptate.
Mersi mult Very Happy
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #15 : Martie 01, 2012, 23:29:42 »

Ai inteles acuma ce e cu invariantii astia?
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #16 : Martie 01, 2012, 23:46:04 »

hmmmm... cred ca am inteles

Pentru cazul meu cu A[mid]<=val ar trebui sa afiseze pozitia cea mai mare pe care se afla numarul cautat, nu? Daca e asa, atunci cat de cat m-am prins.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #17 : Martie 01, 2012, 23:53:51 »

Invariantul a[lo] <= x < a[hi] gaseste ultima pozitie a lui x in sir cand hi = lo + 1 (daca x e in sir).
Memorat
Victor10
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #18 : Martie 02, 2012, 00:18:49 »

Tocmai avusesi o revelatie.
Cred ca m-am prins.
Mersi mult pentru explicatii!
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #19 : Martie 04, 2012, 22:06:12 »

Poti sa incerci problema: http://codeforces.com/contest/158/problem/E
E din ciclul cautare binara doua cautari binare in cautare binara in cautare liniara. Ca sa exersezi invariantii astia.  Succes Thumb up

L.E.: Daca vrei sa iti fortezi creierii, fa-o fara functii.
« Ultima modificare: Martie 04, 2012, 22:11:39 de către Marginean Ninu Ciprian » Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #20 : Martie 04, 2012, 22:31:41 »

Cum ai facut E folosind cautare binara? Huh Ce complexitate ai per total?
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #21 : Martie 04, 2012, 23:02:23 »

Nu am terminat-o, dar ideea mea e asa: Pentru fiecare secunda i de la prima pana la ultima din zi, incercam sa determinam cat de mult poate dormi Ghita, daca incepe sa doarma in secunda i, ignorand cel mult k telefoane. Cat de mult poate dormi (l secunde), determinam cu o cautare binara pe intervalul [0, 86400]. Verificam daca poate dormi incepand din secunda i, timp de l secunde, facand doua cautari binare. Cu una gasim ultimul telefon care se termina inainte de secunda i, si cu cealalta, primul telefon care incepe dupa secunda i + l.

L.E.: Complexitatea ar fi O (S * log S * log N). Unde S e numarul de secunde din intervalul de timp pe care se poate dormi si N e numarul de telefoane. In cazul nostru S=86400.
L.L.E: Totusi ma gandesc ca s-ar putea sa fie gresita solutia asta. Ironic, avand in vedere titlul "Cautarea ta binara este gresita"
« Ultima modificare: Martie 04, 2012, 23:36:50 de către Marginean Ninu Ciprian » Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #22 : Martie 04, 2017, 10:52:45 »

Eu folosesc while(st<dr). Si am grija la setarea mijlocului si la actualizarea intervalului de cautare. In final rezultatul va fi in st.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines