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

Vrlo često, programeri, čak i početnici,lice 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, pretpostavimo da postoji niz s dimenzijom od barem 100000000 elemenata u kojima morate pronaći određeni element. 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 to načelo djelovanjametoda? 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 je željeni broj veći od prosjeka, sve što je na lijevoj strani, tj. Manji od prosječnog elementa, može se odbaciti i ne pretraživati 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 novog područja bit će ¼ cjelokupnog segmenta, tj. (Posljednji element + prosječni 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.

Imat će polje od 1 do h nazvane"massiv", varijabla koja označava donju granicu pretraživanja, nazvana "niz", gornja granica pod nazivom "verh", srednji element pretraživanja je "sredn"; a traženi broj je "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 funkciju div 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 srednji element polja veći od željenog, odbacite lijevu stranu, tj. Srednji element postavljen je kao gornja granica:

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

A ako naprotiv, to učinimo donjom granicom:

drugi niz: = sredn;
kraj;

To je sve što će biti u programu.

Analizirati ćemo kako binarnu metodu izgledati u praksi. Uzmimo sljedeće polje: 1, 3, 5, 7, 10, 12, 18 i tražit ćemo broj 12 u njemu.

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

Budući da je 12 veći od 7, možemo odbaciti elemente 1,3 i 5. Tada ostaje 4 brojeva, 4/2 bez ravnoteže je 2. Stoga će novi srednji element biti 10.

Budući da je 12 veći od 10, odbacujemo 7. Samo 10, 12 i 18 ostaju.

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