Gradivo III razreda u Gimnaziji "Veljko Petrović"

Računarstvo i Informatika

Traženje

Ovde ćemo opisati dva algoritma za proveru da li se traženi elemenat nalazi u nizu.

Sekvencijalno traženje

Ova metoda je jednostavna za implementaciju, ali je spora. Vremensta složenost metode je O(n). Što znači da moramo proći kroz ceo niz da bismo sa sigurnošću mogli tvrditi da li traženi član u nizu.

Type Niz = array [1..N] of integer;

Function ClanNizaSekv(Var X:niz, clan:Integer): Boolean;

Var i, j, pom : integer;

Begin

  ClanNizaSekv := False;

  For i := 1 to N do

      if X[i] = clan

        then Begin

               ClanNizaSekv := True;

               Exit;

             end;

End;

Binarno traženje

Ova metoda je malo interesantnija za implementaciju ali je neuporedivo brža od sekvencijalnog traženja. Vremensta složenost metode je O(log₂n). Ilustrativno, u nizu od milion članova, utvrdićemo pripadnost nizu u najviše 20 pokušaja. Međutim,

Niz mora biti sortiran

Function BS(Trazeni, Prvi, Poslednji:LongInt): LongInt;

Var Srednji : LongInt;

Begin

  BS := 0;

  While Prvi <= Poslednji do

  Begin

    Srednji := (Prvi + Poslednji) div 2;

    if Trazeni < Niz[Srednji]

      then Poslednji = Srednji-1

      else if Trazeni > Niz[Srednji]

             then Prvi = Srednji + 1

             else Begin

                     BS := Srednji;

                     exit;

                  end;

  end;

end;

Postoje razne varijacije ovog algoritma u zavisnosti od toga da li je dozvoljeno ponavljanje članova niza, kada u trenutku pronalaženja traženog elementa moramo još prošetati nizom ulevo do njegovog prvog, odn. udesno do njegovig posl pojavljivanja.

Ovde je prikazan slučaj kada je niz u kome tražimo odr. elemenat globalna promenljiva, ali se niz može preneti i preko parametara.

Direktno traženje

Ova metoda je najbrža vremenski O(1) ali zahteva dodatnu memoriju. Pogodna je za korišćenje uvek kada Vam memorijski resursi nisu kritični. Ipak da biste ovu metodu mogli upotrebiti, potrebno je i da raspon članova niza ne prelazi raspoloživi memorijski prostor. Na primer treba vam da pronadjete da li postoji ili ne neki član a moguće vrednosti ne prelaze 10 000 000 sa raspoloživom memorijom od 16MB.

Var Niz : Array[1..10000] of LongInt;

Var DS  : Array[1..10000000] of boolean;

Prilikom formiranja niza NIZ, potrebno je i u nizu DS postaviti odgovarajući elementa na true. Sada ako Vam je potrebna informcija da li je neki član u nizu NIZ, samo pogledate u niz DS na nj. mesto.

  if DS[broj] then ... {ima ga} else ... {nema ga}

Raspon članova originalnog niza, ne sme prelaziti raspoloživu memoriju