|
Algoritam binarnog pretraživanja polja je brži od slijednog
algoritma, ali ovdje ipak nešto moramo znati o podacima koje pretražujemo.
Naime, kako bi algoritam binarnog pretraživanja bio točan, polje koje
pretražujemo mora biti sortirano.
Vidjeli smo da algoritam slijednog pretraživanja polja pregledava redom elemente polja.
Sada nas zanima kako radi ovaj algoritam.
Algoritam binarnog pretraživanja radi na sličnom principu kao kada pretražujemo
telefonski imenik. Naime, algoritam prvo usporedi srednji element polja s traženim
elementom. Ako to nije element koji nas zanima, sada zna treba li pogledati u prvu
polovicu ostatka polja, ili u drugu jer zna je li traženi element manji ili veći od
elementa s kojim smo ga usporedili.
Pogledajmo sada pseudokod ovog algoritma:
BIN-PRETRAZIVANJE(A, low, high, n)
- if low < high
- then temp <- (high+low)/2
- if A[temp] < n
- then BIN-PRETRAZIVANJE(A, low, temp, n)
- else if A[temp] > n
- BIN-PRETRAZIVANJE(A, temp, hign, n)
- else return temp
- return -1
Vidimo da ovaj algoritam kao parametre prima polje A,
minimalni low i maksimalan high
indeks dijela polja u kojem pretražujemo, te element n
koji tražimo. Kada prvi puta pozivamo ovu proceduru, pisemo da nam je
low jednako pocetnom indeksu polja, a
high zadnjem indeksu polja.
Primjetimo još da je, u najgorem slučaju (tj. kada se traženi element ne nalazi u polju),
potrebno reda veličine lg(n) koraka za izvršenje ovog algoritma
jer polje stalno dijelimo na dva dijela i pretražujemo u jednom od ta dva dijela.
|
