Binarno pretraživanje je jedan od najlakših načina da pronađete element u nizu

Često programeri, čak i početnici,suočeni su sa činjenicom da postoji skup brojeva u kome je potrebno pronaći određeni broj. Ova kolekcija se zove niz. A da biste pronašli željeni element u njemu, postoji mnogo načina. Ali najjednostavniji među njima se s pravom može smatrati binarnim pretraživanjem. Šta je ovaj metod? A kako implementirate binarnu pretragu? Pascal je najjednostavnije okruženje za organizovanje ovakvog programa, pa ćemo ga koristiti za učenje.

Prvo ćemo analizirati koje su prednosti ove metode, jer na taj način možemo razumeti

koja je svrha proučavanja ove teme.Dakle, pretpostavimo da postoji niz sa najmanje 100.000.000 elemenata u kojem treba da pronađete određeni. Naravno, ovaj problem se lako može rešiti jednostavnom linearnom pretragom, u kojoj ćemo koristiti petlju da uporedimo željeni element sa svim elementima u nizu. Problem je što će implementacija ove ideje trajati predugo. U jednostavnom Pascal programu za nekoliko procedura i sa tri reda glavnog teksta ovo nećete primetiti, ali kada započnete manje-više velike projekte sa mnogo grana i dobrom funkcionalnošću, gotovom programu će biti potrebno predugo da se učita. Naročito ako računar ima loše performanse. Zbog toga postoji binarna pretraga, koja skraćuje vreme pretrage najmanje za polovinu.

Dakle, koji je princip rada ovogametod? Odmah treba reći da binarno pretraživanje ne radi ni u jednom nizu, već samo u sortiranom skupu brojeva. U svakom sledećem koraku uzima se srednji element niza (znači po broju elementa). Ako je željeni broj veći od proseka, onda se sve što je levo, odnosno manje od srednjeg elementa, može odbaciti i ne tražiti tamo. I obrnuto, ako je manji od proseka - među onim brojevima na desnoj strani, ne morate da tražite. Zatim ćemo izabrati novu oblast za pretragu, gde će prvi element biti srednji element čitavog niza, a poslednji će ostati poslednji. Prosečan broj nove oblasti biće ¼ celog segmenta, odnosno (poslednji element + srednji element čitavog niza) / 2. Opet se vrši ista operacija – poređenje sa prosekom niza. Ako je željena vrednost manja od prosečne, desnu stranu odbacujemo i radimo isto dalje, sve dok se ovaj srednji element ne pokaže željenim.

Naravno, najbolje je pogledati primer kako se piše binarno pretraživanje. Bilo koji Pascal će poslužiti ovde - verzija nije važna. Hajde da napišemo jednostavan program.

Sadržaće niz od 1 do h tzv"massiv", promenljiva koja označava donju granicu pretrage pod nazivom "niz", gornju granicu pod nazivom "verh", srednju pretragu pod nazivom "sredn"; a potreban broj je „isk”.

Dakle, prvo dodeljujemo gornju i donju granicu intervala pretrage:

niz: = 1;
verh: = h + 1;

Zatim organizujemo ciklus "dok je donja manja od gornje granice":

Dok niz <verh - 1 do
почети

U svakom koraku delimo segment sa 2:

sredn: = (niz + verh) div 2; {koristite funkciju div jer delimo bez ostatka}

Svaki put kada proverimo. Ako je prosek jednak željenom, prekidamo petlju, pošto je traženi element već pronađen:

íf sredn = isk onda break;

Ako je srednji element niza veći od željenog, odbacite levu stranu, odnosno dodelite srednji element kao gornju granicu:

ako masiv [sredn]> isk onda verh: = sredn;

A ako naprotiv, onda to činimo donjom granicom:

else niz: = sredn;
крај;

To je sve što će biti u programu.

Da vidimo kako će binarni metod izgledati u praksi. Uzmimo niz ovako: 1, 3, 5, 7, 10, 12, 18 i potražimo u njemu broj 12.

Ukupno imamo 7 elemenata, tako da će sredina biti četvrti, njena vrednost je 7.

1

3

5

7

10

12

18

Pošto je 12 veće od 7, možemo odbaciti stavke 1,3 i 5. Tada nam ostaju 4 broja, 4/2 bez ostatka je 2. Dakle, novi srednji element će biti 10.

7

10

12

18

Pošto je 12 veće od 10, odbacujemo 7. Ostaje samo 10, 12 i 18.

Ovde je srednji element već 12, ovo je željeni broj. Zadatak završen – pronađen broj 12.