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

Vrlo često, programeri, čak i početnici, suočeni sa činjenicom da postoji niz brojeva, koji mora pronaći određeni broj. To je ova kolekcija se zove niz. I da stvari u njemu, postoji bezbroj načina. Ali najjednostavniji od njih može se smatrati binarno pretraživanje na desnoj strani. Ono što je ova metoda? I kako implementirati binarni pretraživanje? Pascal je najlakši okruženje za organizaciju takvog programa, tako da ćemo ga koristiti za proučavanje.

Prvo, analizirati, koje su prednosti ove metode, to je tako da možemo shvatiti, koja je svrha u studiji teme. Dakle, da imaju niz od dimenziju najmanje 100000000 elemenata, koje je potrebno pronaći neke. Naravno, ovaj problem se može lako riješiti jednostavno linearno pretraživanje, u kojem smo se koriste ciklus će uporediti potrebne element sa svim onim koji su u nizu. Problem je u tome što implementacija ove ideje će uzeti previše vremena. Na jednostavan Pascal program u nekoliko tretmana, i tri linije glavnog teksta, nećete primijetiti, ali kad smo došli do više ili manje velike projekte sa velikim brojem grana i dobre funkcionalnosti, program će biti spremni da se učita predugo. Pogotovo ako je računar slab učinak. Prema tome, postoji binarni pretraživanje, što smanjuje vrijeme traženja najmanje dva puta.

Dakle, ono što je princip rada ove metode? Odmah treba reći da je binarna pretraga radi se ni u kom nizu, ali samo na sortirane skup brojeva. Na svakom koraku uzima srednji element niza (što znači da se broj elemenata). Ako je potrebno broj je veći od prosjeka, onda sve što je ostalo, to je manje od prosjeka u ćeliju, mogu biti odbačeni i da ne gleda tu. Nasuprot tome, ako je manji od prosjeka - među onima brojeve u redu, ne može tražiti. Zatim odaberite novu pretragu područje, gdje će prvi element biti srednji element čitavog niza, a posljednji i posljednji volja. Prosječan broj novih polje će biti ¼ svih segmenta, to jest, (zadnji element + sredinom element čitavog niza) / 2. Opet, ista operacija se izvodi - poređenje sa prosječnim brojem niza. Ako je ciljna vrijednost manja od prosjeka, odbacujemo sa desne strane, ali i dalje da radi, do sada ovaj srednji element ne bi želji.

Naravno, najbolje je pogledati primjer kako pisati binarno pretraživanje. Pascal ovdje će odgovarati nikome - verzija nije važno. Hajde da napišem jednostavan program.

To je niz od 1 do h pod nazivom "massiv", varijabla ukazuje na donje granice pretraživanje, pod nazivom "niz", gornja granica, pod nazivom "Verh", prosječna pretraživanja izraza - "kil"; i potreban broj - "isk".

Dakle, prvo smo dodijeliti gornje i donje granice za pretraživanje opseg:

niz: = 1;
Verh: = h + 1;

Onda organizirati ciklus "do dna je manje u odnosu na gornju granicu":

Dok je niz početi

Na svakom koraku, dijelimo segmentu 2:

kil: = (niz + Verh) div 2; {Koristite funkciju div, jer je podjela bez ostatka}

Svaki put pregleda. Budući da je stavka već utvrđeno da li je medij se želi, prekinuti ciklus:

іf kil = isk onda break;

Ako je srednji element niza više od željenog, bacite lijevoj strani, to jest, gornje granice prosjeka imenovati elementa:

ako massiv [kil]> isk tada Verh: = kil;

A ako naprotiv, čini donje granice:

drugi niz: = kil;
završiti;

To je sve što će biti u programu.

Uzmimo u obzir kako će izgledati binarnih metoda u praksi. Razmotrimo ovaj niz: 1, 3, 5, 7, 10, 12, 18 i da će tražiti broj 12.

Ukupno imamo 7 elemenata, tako da će se u četvrtom srednje, vrijednost 7.

Jer je više od 12, 7, 1.3 i 5 elemenata, možemo odbaciti. Onda imamo broj 4, 4/2 bez ostatka je 2. Dakle, novi element će biti u prosjeku 10.

Od 12 je veći od 10, odbacimo 7. ostaje samo 10, 12 i 18 godina.

Evo, srednji element je već 12, to je potreban broj. Ovaj zadatak je završen - broj 12 pronađeno.