Binarno pretrazivanje

Pretraživanje je proces koji za cilj ima pronalaženje elementa niza, liste, stabla, ili neke druge strukture podataka, koji zadovoljeva unapred definisani kriterijum.

Ukoliko sa sigurnošću znamo da je niz koji pretražujemo uređen u rastućem ili opadajućem poretku, onda za pretraživanje možemo iskoristiti neki od algoritama koji koristi ovu činjenicu kako bi skratio vreme traženja. Jedan od takvih algoritama je binarno pretraživanje. Ovaj algoritam vrši pretraživanje niza tako što prvo upoređuje traženi element sa središnjim elementom niza. Ukoliko središnji element nije jednak traženom elementu, zahvaljujući činjenici da je niz rastući ili opadajući, algoritam određuje u kojoj polovini se može naći traženi element, a drugu polovinu odbacuje. Isti proces se ponavlja na dobijenoj polovini sve dok se ne pronađe traženi element ili dok u podnizu nakon deljenja ne ostane ni jedan element, što bi značilo da niz ne sadrži traženi element.Napredna funkcija vrši binarno pretraživanje u rastućem nizu:

int trazi(int a[],int n,int t)
{
   int donji, gornji, srednji;
   donji=0;
   gornji=n-1;
   while(donji<=gornji)
   { 
       srednji=(donji+gornji)/2;
       if(a[srednji]==t) return(srednji);
 
       if(t<a[srednji]) gornji=srednji-1;
       else donji=srednji+1;
   }
   return(-1);
}

Na početku se posmatra ceo niz, tako da su početne vrednosti donje i gornje granice jednake nultom i poslednjem indeksu niza. Zatim se određuje središnji element i ispituje da li je on jednak traženom elementu. Ukoliko je to traženi element, funkcija vraća njegov indeks. Usuprotnom proverava se da li je traženi element manji ili veći od središnjeg elementa.Ako je traženi elemant manji, odbacuje se gornji podniz tako što se gornja granica pomera na prvu poziciju ispod središnjeg elementa. U suprotnom, odbacuje se donji podniz tako što se donja granica pomera na prvu poziciju iznad središnjeg elementa. Nakon toga čitav postupak se ponavlja na odabranom podnizu sve do pronalaženja traženog elementa ili do trenutka kada podniz više ne sadrži ni jedan element. Ukoliko je niz koji se pretražuje opadajući, izbor polovine niza koja se dalje pretražuje se obavlja na suprotan način nego što je to u slučaju rastućeg niza.

  • Više o ovoj temi možete da pronađete na sledećem linku: SPA2

Nazad

 
binarno_pretrazivanje.txt · Last modified: 2011/12/08 20:57 by bojan.grabez
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki