Pretraživanje niza
U ovoj lekciji želimo da proverimo da li se u nekoj kolekciji nalazi određeni element, neki važan broj ili podatak, koji nam je možda potreban u nekim daljim istraživanjima ili drugim delovima programa. Naučićemo dva načina na koja možemo da sprovedemo pretragu našeg niza (načina ima više, mi ćemo pomenuti samo dva).
Nizovi omogućavaju rad sa velikim brojem elemenata, što znači da se može manipulisati sa velikim količinama podataka. Sa druge strane, obrada velikog broja podataka zahteva više vremena, pa su potrebni efikasniji algoritmi. Zbog toga su razvijene i različite metode koje se najčešće koriste, kao što su pretraživanje i sortiranje elemenata niza.
Pretraživanjem se, u opštem slučaju, proverava da li se zadata vrednost pojavljuje u nekom nizu vrednosti.
Definicija 2: Pretraživanje je proces nalaženja elemenata niza, koj isadrži određeni podatak koji zovemo ključ.
Drugim rečima, pretraživanje niza predstavlja pronalaženje određenog elementa niza koji zadovoljava neki unapred zadat uslov (recimo tačno određenu vrednost) i utvrđivanje indeksa traženog elementa.
Za pretraživanje niza su razvijeni različiti algoritmi, od kojih se najčešće koriste: linearno pretraživanje i binarno pretraživanje. Koji će algoritam biti korišćen za rešavanje određenog problema, pre svega zavisi od suštine samog problema i od toga da li se traži efikasnije ili jednostavnoije rešenje (jer to ne mora da ide uvek jedno sa drugim).
Efikasnost pretraživanja meri se (uglavnom) prosečnim brojem poređenja koje je potrebno izvesti u postupku traženja različitih vrednosti u određenom nizu.
LINEARNO (SEKVENCIJALNO) PRETRAŽIVANJE
Metoda linearnog pretraživanja je najjednostavnija i najkorišćenija, mada ne i najefikasnija. Sastoji se u sukcesivnom upoređivanju svakog elementa sa zadatom vrednošću. Drugim rečima, ispituje se jedan po jedan element niza sve dok se ne nađe odgovarajući element ili dođe do kraja niza.
Posmatrajmo NPR, niz brojeva od sedam elemenata (niz[7]). Pretpostavimo, takođe, da su brojevi u nizu već sortirani u rastućem redosledu, tj. zadovoljavaju uslov:
niz[0]<niz[1]<niz[2]<niz[3]<niz[4]<niz[5]<niz[6]
Pretaživanje ovog niza sastoji se u tome da pronađemo element niza čija je vrednost jednaka promenljivoj dati_broj.
Metodom linearnog pretraživanja svaki element niza niz uporedićemo s promenljivom dati_broj.
Postupak se ponavlja dok se ne ispuni:
niz[i]=dati_broj (ukoliko postoji traženi broj), ili sve dok nije
niz[i]>=dati_broj (ukoliko se dati_broj ne nalazi u nizu).
Maksimalni broj koraka (poređenja) metodom linearnog pretraživanja je jednak 7 (u ovom slučaju), odnosno u opštem slučaju, jednak je broju elemenata niza.
Primer: Program koji se u datom nizu a[5] pronalazi element jednak vrednosti dati_broj i prikazuje na ekranu njegov indeks
/*ispis indeksa traženog broja*/
BINARNO PRETRAŽIVANJE
Uređeni niz (recimo niz[n]) može se brže pretraživati metodom algoritma binarnog pretraživanja ili algoritam deljenja na pola. Postupak se sastoji u sledećem:
- pronađemo srednji element niza sa indeksom s=(n-1)/2,
- proverimo da li je to nađeni indeks, tj. da li je niz[s]=dati_broj,
- ako jeste,prekidamo dalje pretraživanje,
- ako nije, proveravamo da li važi niz[s]<dati_broj i onda pretražujemo samo deo deo niza u intervalu od 0 do s-1,
- ako je niz niz[s]>dati_broj , onda pretražujemo deo niza od s+1 do n-1,
Na ovaj način je prepolovljen niz (interval niza) za pretraživanje. U daljem postupku i ovaj (prepolovljeni) interval pretražujemo metodom deljenja na pola, sve dok ne nađemo traženi element (dati_broj),