infoarena

Comentarii la postul http://infoarena.ro/blog/cautare-binara

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!

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.

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

Atunci nu merge pentru cazul in care elementul cautat se afla pe prima pozitie :))

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

#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);
}

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

7
1 3 3 4 5 6 7
1


Pe prima linie numarul de elemente. Pe a doua elementele. Pe a treia elementul cautat

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

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?

Ai dreptate, asa e si la mine. Nu stiu, ma depaseste. O sa las pe altcineva mai in masura sa iti raspunda.  :-'

Ok, mersi oricum pentru efortul depus :)

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).

Aoleu aoleu aoleu.
Ai dreptate.
Mersi mult :D

Ai inteles acuma ce e cu invariantii astia?

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.

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

Tocmai avusesi o revelatie.
Cred ca m-am prins.
Mersi mult pentru explicatii!

Poti sa incerci problema: http://codeforces.com/contest/158/problem/E (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 :thumbup:

L.E.: Daca vrei sa iti fortezi creierii, fa-o fara functii.

Cum ai facut E folosind cautare binara? ??? Ce complexitate ai per total?

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"

Eu folosesc while(st<dr). Si am grija la setarea mijlocului si la actualizarea intervalului de cautare. In final rezultatul va fi in st.