Binarno pretraživanje jedan je od najjednostavnijih načina pronalaženja elementa u nizu

Vrlo često, programeri, pa čak i početnici, suočavaju se s činjenicom da postoji skup brojeva u kojima je potrebno pronaći određeni broj. Ova zbirka se naziva polje. I pronaći pravi element u njemu, postoji mnogo načina. No, najjednostavniji među njima za pravo može se smatrati binarnim pretraživanjem. Koja je metoda? A kako implementirati binarnu pretragu? Pascal je najjednostavniji medij za organiziranje takvog programa, pa ćemo ga koristiti za studij.

Prvo ćemo analizirati što su prednosti ove metode, nakon svega, tako da možemo razumjeti, što je točka u proučavanju ove teme. Dakle, neka je imaju niz sa dimenziju najmanje 100000000 elemenata, koje je potrebno kako bi pronašli neke. Naravno, ovaj problem može lako riješiti jednostavne linearne pretraživanje, u kojem smo pomoću ciklus će usporediti potrebne elemente sa svima onima koji su u polju. Problem je u tome što će implementacija ove ideje trajati predugo. Na jednostavan Pascal programa u nekoliko tretmana, te tri linije glavni tekst, nećete primijetiti, ali kad smo došli do više ili manje velikih projekata s velikim brojem grana i dobru funkcionalnost, program će biti spreman da se učita predugo. Pogotovo u slučaju da računalo ima lošu izvedbu. Stoga, postoji binarno pretraživanje, koje smanjuje vrijeme pretraživanja barem dvaput.

Dakle, koji je princip ove metode? Vrijedno je spomenuti da binarno pretraživanje ne funkcionira u bilo kojem nizu, već samo u sortiranom skupu brojeva. U svakom sljedećem koraku uzima se srednji element polja (koji se odnosi na broj elementa). Ako želite broj više znači, onda sve što je na lijevoj strani, tj. manje od prosječnog elementa, može se odbaciti i ne pretražiti tamo. Isto tako, ako je manje od prosjeka, među brojevima s desne strane, ne možete ih tražiti. Zatim ćemo odabrati novo područje pretraživanja, gdje će srednji element cijelog polja biti prvi element, a zadnji će ostati zadnji. Prosječan broj novih područja bit će frac14 je ukupna duljina, to jest (posljednji element + srednji element cijelog niza) / 2. Opet, izvedena je ista operacija - usporedba s prosječnim brojem polja. Ako je željena vrijednost manja od prosjeka, odbacite desnu stranu i učinite isto dok ne pronađete ovaj srednji element.

Naravno, najbolje je pogledati primjer kako je napisano binarno pretraživanje. Pascal ovdje je prikladan za svakoga - inačica nije važna. Napišimo jednostavan program.

To je niz od 1 do h pod nazivom „massiv”, varijabla ukazuje na donju granicu za pretraživanje, pod nazivom „niz”, gornja granica, pod nazivom „verh”, prosječna traženi pojam - „sredn” - kao i potreban broj - „ISK”.

Dakle, prvo dodijelite gornju i donju granicu intervala pretraživanja:

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

Tada organiziramo ciklus "dok je dno manje od gornje granice":

Dok niz < verh - 1 do
početi

U svakom koraku podijelite segment za 2:

sredn: = (niz + verh) div 2- {koristite div funkciju, jer dijelimo ostatak}

Svaki put kad provodimo ček. Ako je prosjek jednak željenom, prekinemo ciklus jer je već pronađen željeni element:

ako sredn = isk onda pauza;

Ako je prosječni element polja veći od onog kojeg tražimo, bacite lijevu stranu, tj. Dodijelimo srednji element gornjoj granici:

ako je masiv [sredn]> isk tada verh: = sredn;

I ako naprotiv, onda to učinimo nižom granicom:

drugi niz: = sredn-
kraj;

To je sve što će biti u programu.

Analizirat ćemo kako će binarnom metodom izgledati u praksi. Uzmimo takav niz: 1, 3, 5, 7, 10, 12, 18 i tražimo broj 12 u njemu.

Ukupno imamo 7 elemenata, pa će prosjek biti četvrti, vrijednost 7.

Budući da je 12 veći od 7, elementi 1,3 i 5 mogu se odbaciti. Zatim imamo 4 brojeva lijevo, 4/2 bez preostalih je 2. Dakle, novi srednji element će biti 10.

Budući da je 12 više od 10, odbaci 7. Samo 10, 12 i 18 su ostali.

Ovdje je srednji element već 12, to je potreban broj. Zadatak je završen - pronađen je broj 12.