Pretraživanje po binarnom - jedan od najjednostavnijih načina da se element u nizu

Vrlo često, programeri, čak i početnici, suočeni s činjenicom da postoji skup brojeva, koji mora pronaći određeni broj. To je ovaj skup se naziva polje. A kako bi pronašli stavke u njoj, postoji bezbroj načina. No, najjednostavnija od njih može se smatrati binarno pretraživanje na desnoj strani. Što je ova metoda? A kako provesti binarno pretraživanje? Pascal je najlakši okruženje za organizaciju takvog programa, tako da ćemo ga koristiti za proučavanje.

Prvo, analizirati, što su prednosti ove metode, to je tako možemo razumjeti, što je točka u proučavanju 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 da je provedba ove ideje će uzeti previše vremena. 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 ako je računalo je slab učinak. Dakle, tu je pretraživanje po binarnom, što smanjuje vrijeme pretraživanja barem dvaput.

Dakle, ono što je princip rada ove metode? Odmah bi trebalo reći da pretraživanje po binarnom radi ni na koji niz, ali samo na sortiranog niza brojeva. U svakom stupnju uzeti srednji element polja (znači broj elementa). Ako je potreban broj veći od prosjeka, onda je sve što je ostalo, to je manja od prosječne stanici, može biti odbačena, a ne gledati tamo. Isto tako, ako je manje od prosjeka - među tim brojevima na desnoj strani, ne možete tražiti. Zatim odaberite novo područje za pretraživanje, gdje će prvi element bude srednji element cijelog niza, a posljednji i posljednji volja. Prosječan broj novih polja će biti ¼ svih segmenta, odnosno, (zadnjem elementu + srednji element cijelog niza) / 2. Opet, ista operacija se izvodi - usporedba s prosječnim brojem polja. Ako je ciljna vrijednost je manja od prosjeka, odbacujemo desnu stranu, a također treba učiniti sljedeće, do sada to srednji element ne bi poželjno.

Naravno, najbolje je da pogledate primjer kako napisati binarnog pretraživanja. Pascal ovdje će odgovarati nikome - verzija nije važno. Idemo napisati jednostavan program.

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

Dakle, prvo ćemo dodijeliti gornju i donju granicu traženja raspona:

niz: 1;
verh: = h + 1;

Zatim organizira ciklus „dok je dno ispod gornje granice”:

Dok niz početi

Na svakom koraku, podijelimo segment 2:

sredn: = (+ niz verh) div 2; {Uporaba funkcije div, jer bez podjele ostatak}

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

íf sredn = ISK puknuti;

Ako je srednji element polja više nego što želite, bacite lijevu stranu, odnosno gornja granica od prosjeka elementa imenovati:

Ako massiv [sredn]> ISK zatim verh: = sredn;

A ako naprotiv, čini donji granicu:

drugi niz: = sredn;
kraj;

To je sve što će biti u programu.

Razmotrimo kako će izgledati binarni način u praksi. Razmotrite ovo polje: 1, 3, 5, 7, 10, 12, 18 i to će tražiti broj 12.

Ukupno imamo 7 elemenata, tako da će četvrti srednje, vrijednost 7.

Budući da je više od 12, 7, 1,3 i 5 elemenata, može odbaciti. Tada smo dobili broj 4, 4/2 bez Ostatak je 2. Dakle, novi element bit će prosjek od 10.

Od 12 je veći od 10, što odbaciti 7. ostaje samo 10, 12 i 18.

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