Pripreme za algoritme(10)

Danas ćemo se baviti kako što brže pronaći element x u niz n. Današnja tema je binarno pretraživanje, a kod je pisan u Pascalu. Bitno je reći da je binarno pretraživanje vrlo ključno za ostvaranje dobrih rezultata na osnovnoškolskoj i srednjoškolskoj skupini.

Binarno pretraživanje

Sekvencijalno pretraživanje niza sastoji se u tome da se provjeravaju sve komponente niza po redu, počevši od prve, sve dok se ne nađe tražena vrijednost ili se ne dođe do kraja niza. Ovu je metodu jednostavno razumjeti, ali je često nedjelotvorna.

Binarno pretraživanje u manje koraka dolazi do rješenja. Bitno je da se ova metoda primjenjuje na sortiranom nizu. Ideja je sa se zadani niz podijeli na dva dijela i zatim provjeri pripada li traženi broj lijevom ili desnom dijelu. Nakon toga se ponovno dijeli onaj dio kojem broj pripada. Postupak se ponavlja sve dok nije pronađen zadani broj ili dijeljenje više nije moguće. Opisan je postupak za rastući niz.

• d je oznaka za donju granicu indeksa niza (d=1 na početku)
• g je oznaka za gornju granicu niza (g=n na početku)
• odredi se indeks komponente na sredini niza (p=(d+g) div 2)
• izvrši se usporedba komponente K[p] s traženom vrijednošću (TV)
• ako je K[p]=TV postupak se prekida
• ako je K[p]<TV znači da se tražena vrijednost nalazi na desnoj strani niza – pretraživanje se nastavlja samo za taj dio niza. Donja granica pretraživanja se pomiče d=p+1, a gornja ostaje ista
• ako je K[p]>TV znači da se tražena vrijednost nalazi na lijevoj strani niza – gornja granica se pomiče g=p-1, a donja granica ostaje ista kao u prethodnom pretraživanju
• pretraživanje prestaje kada je pronađena vrijednost ili kada donja granica postane veća od gornje (zaključujemo da tražena vrijednost nije u nizu)

program binarno_pretrazivanje;

var i,n:integer;

niz:array[1..100] of integer;

tv,p,d,g:integer;

begin

write('Upiši broj elemenata: ');

readln(n);

for i:=1 to n do begin

write('Upiši ',i,'. broj');

readln(niz[i]);

end;

write('Upiši traženu vrijednost: ');

readln(tv);

d:=1; g:=n;

repeat

p:=(d+g)div 2;

if niz[p]=tv then write ('Tražena vrijednost je na ',p,'. tom mjestu')

else if niz[p]<tv then d:=p+1

else g:=p-1;

until (niz[p]=tv)or (d>g);

if (d>g)then write('Tražena vrijednost nije u skupu brojeva');

end.

Toliko od nas za danas. Nastavljat ćemo sa analiziranje i pojašnjavanjem algoritama koji su na popisu za natjecanje Infokupa 2013.