Serijsko (sekvencijalno - linearno) pretraživanje

 

Proces pretraživanja je vrlo čest u obradi podataka, pa je poznavanje metoda i tehnika organizacije podataka pretraživanja je vrlo važno.

 Suporter

Standardno postoje dvije osnovne vrste strategija pretraživanja:

   Slijepo pretraživanje
(blind, uninformed search)
   Usmjereno pretraživanje (directed, informed, heuristic search)
Algoritama za pretraživanje treba da ima sljedeća svojstva:
1. Potpunost (completeness) – algoritam je potpun ako pronalazi rješenje uvijek kada ono postoji
2. Optimalnost (optimality, admissibility) – algoritam je optimalan ako pronalazi optimalno rješenje (ono s najmanjom cijenom)
3. Prostorna složenost
4. Vremenska složenost

Serijsko pretraživanje podrazumjeva prolazak kroz sve članove niza od prvog do poslednjeg i poređenje sa traženim elementom.

 

Linearno pretraživane je najjednostavnije i najčešće korišteno pretraživanje. Takođe je i najsporije jer prolazi kroz sve elemente niza pa tako ako imamo niz sa 100.000 elemenata i element koji mi tražimo nalazi se na samom kraju, recimo na poziciji 99.999 onda će pretraga trajati dosta dugo.

 

Algoritam ima dvije ulazne varijable koje koristi trazeni, i pozicija.

U varijablu trazeni se pohranjuje vrijednost koja se traži, a u varijablu pozicija se pohranjuje pozicija na kojeme se traženi element nalazi.

Algoritam se sastoji od jedne for petlje koja kao početnu vrijednost ima 0, kao krajnju vrijednost ima varijablu velicinu, u kojoj se nalazi velicina niza kojeg se pretražuje.

Ako-kad se nađe tražena vrijednost u nizu onda se u varijablu pozicija sprema pozicija na kojoj se ta vrijednost nalazi u zadatom nizu.

Analiziraj primjer i dijagram toka koji predstavlja serijsku pretragu:

dijagram serijske pretrage

Linear search is the simplest search algorithm; it is a special case of brute-force search.

 

Linear Search Example

List of Data:58,62,75,88,92,105

Data to be searched is 75

Primjer serijske pretrage

 

 

 

 

 

 

 

 

copyright M2M
BL-2011