Pri razvoju algoritama za rješavanje mnogih problema, problem se često javlja provođenjem pretraživanja određene skupine podataka prema zadanim kriterijima. Kada se istražuje uređena ili neuređena sekvenca, pretraga se može izvesti različitim metodama. U općenitom slučaju, za rješavanje problema pretraživanja, uzima se u obzir određeni niz podataka u kojem je potrebno pronaći zadani element.
Instrukcije
Korak 1
Najlakši način za pronalaženje poznatog elementa u nizu podataka je prelazak preko njegovih vrijednosti. Ovaj algoritam je optimalan za male količine informacija. Njegova suština leži u prelaženju poznate sekvence podataka (niza) i usporedbi svakog elementa sa željenom vrijednošću. Ako se pronađe podudaranje, ovisno o navedenim kriterijima, pretraživanje se može dovršiti ili nastaviti do kraja niza.
Korak 2
Međutim, uprkos jednostavnosti primjene ove metode, njezina je upotreba nepoželjna u nizovima koji sadrže velike količine informacija, jer to značajno povećava intenzitet resursa algoritma. Da bi se u ovom slučaju optimiziralo pretraživanje, bolje je prethodno sortirati vrijednosti u polju i implementirati algoritme pretraživanja: binarnim stablom, Fibonaccijevim stablom, metodom ekstrapolacije.
Korak 3
Kada radite sa uređenim nizom, koristite efikasniji algoritam - binarnu metodu pretraživanja. Njegova suština leži u činjenici da se u procesu nabrajanja granica intervala približavaju jedna drugoj, sužavajući tako područje pretraživanja. Usporedite vrijednost koju tražite s numeriranim elementom niza. Ako se uzorak podudara s elementom, problem se smatra riješenim. Ako je željena stavka veća od srednjeg elementa, tada se mora izvršiti daljnje pretraživanje u dijelu niza koji se nalazi desno od srednjeg elementa (od početka niza do srednjeg elementa-1). Ako je pretraga manja od srednjeg elementa, pretraga se nastavlja u dijelu niza od srednjeg do posljednjeg elementa. Utvrdivši novo područje za pretraživanje, opisani algoritam se ponavlja, identificirajući podudaranja ili sužavajući područje obrade. Ova shema je ispravna za silazni niz.
Korak 4
Posebni problemi pronalaženja minimalnog ili maksimalnog elementa u datoj sekvenci rješavaju se dodjeljivanjem početnog elementa željenim. Dalje se vrši sekvencijalno nabrajanje preostalih vrijednosti niza: drugo s prvim, treće s prvim itd. Kada se uspoređuje vrijednost uzeta kao standard, postaje jasno postoji li element u nizu koji je više u skladu s danim uvjetom (minimum ili maksimum). Kada se jedan pronađe, to se već uzima kao standard, a nabrajanje se nastavlja od trenutne pozicije do kraja niza. Kao rezultat, minimalna (ili maksimalna) vrijednost u ovoj grupi je element koji je zadnji put prepoznat kao standard.
