Pretraživanje niza
Pretraživanjem želimo da proverimo da li se u nekom nizu 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 zasad 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 jednostavnije 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 na primer, 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*/
Metoda Linearne pretrage niza se koristi kada tražimo element u nizu koji nije ni na koji način uređen - kod takvog niza je jedini način pretrage traženje redom - prolazak kroz sve članove niza, jedan po jedan.
Ako imamo niz koji je uređen na neki način (rastući, opadajući npr), u tom slučaju se može koristiti i neka od metoda pretraga koja ne traži prolazak kroz ceo niz. Ako je na primer niz rastući (svaki sledeći element je veći od prethodnog), možemo na primer da koristimo binarnu pretragu koja je opisana u nastavku:
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),