Binarno iskanje je eden izmed najlažjih načinov za iskanje elementa v matriki

Pogosto se programerji, tudi začetniki, soočajo z dejstvom, da obstaja niz številk, v katerih je treba najti določeno število. Ta zbirka se imenuje matrika. In najti pravi element v njem, obstaja veliko načinov. Toda najpreprostejši med njimi po pravici se lahko šteje za binarno iskanje. Kakšna je metoda? In kako izvajati binarno iskanje? Pascal je najpreprostejši medij za organizacijo takega programa, zato ga bomo uporabili za študij.

Najprej bomo analizirali, kakšne so prednosti te metode, tako da lahko razumemo, kakšna je točka pri preučevanju te teme. Torej, domnevajte, da obstaja matrika z dimenzijo najmanj 100000000 elementov, v kateri morate najti določeno. Seveda, lahko ta problem enostavno rešiti z navadno linearno iskanje, v katerem se uporablja cikel bo primerjal potrebno element z vsemi tistimi, ki so v matriki. Težava je, da bo izvajanje te ideje trajalo predolgo. V preprosti Pascal programa v več zdravljenja in tri vrstice v glavnem besedilu, ne boste opazili, ko pa pridemo do bolj ali manj velike projekte z velikim številom podružnic in dobre funkcionalnosti, bo program pripravljen, da se naloži predolgo. Še posebej, če ima računalnik slabe rezultate. Zato obstaja binarno iskanje, ki zmanjša čas iskanja vsaj za dvakrat.

Torej, kaj je načelo te metode? Treba je omeniti, da binarno iskanje ne deluje v nobeni matriki, temveč samo v razvrščenem nizu številk. Na vsakem naslednjem koraku se vzame srednji element matrike (ki se nanaša na številko elementa). Če želite število več pomeni, potem je vse, kar je na levi, to je manj od povprečnega elementa, lahko zavržemo in ne iščemo tam. Nasprotno, če je manj kot povprečje, med številkami na desni strani jih ne morete iskati. Nato bomo izbrali novo območje iskanja, kjer bo prvi element celotnega polja prvi element, zadnji pa bo zadnji. Povprečno število novih območij bo frac14 je skupna dolžina, to je (zadnji element + srednji element celotne matrike) / 2. Spet se izvede ista operacija - primerjava s povprečnim številom matrike. Če je želena vrednost manjša od povprečja, zavrite desno stran in storite enako, dokler se ne najde ta srednji element.

Seveda je najbolje, da pogledamo primer, kako je zapisano binarno iskanje. Pascal tukaj je primeren za vsakogar - različica ni pomembna. Napišite preprost program.

To je niz 1 do h pod imenom "MASSIV", spremenljivka označuje spodnjo mejo za iskanje, ki se imenuje "niz" je zgornja meja, ki se imenuje "verh", povprečni iskalni izraz - "sredn" - in potrebno število - "ISK".

Torej najprej določite zgornje in spodnje meje iskalnega intervala:

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

Potem organiziramo cikel "medtem ko je dno manj kot zgornja meja":

Medtem ko niz < verh - 1 do
začeti

Na vsakem koraku razdelite segment za 2:

sredn: = (niz + verh) div 2- {uporabite funkcijo div, ker delimo preostanek}

Vsakič, ko preverjamo. Če je povprečje enako želeni, prekinemo cikel, ker je želen element že ugotovljen:

če sredn = isk nato prelomi;

Če je povprečni element matrike večji od tistega, ki ga iščemo, zavrite levo stran, to pomeni, da srednjemu elementu dodelimo zgornjo mejo:

če masiv [sredn]> isk potem vrh: = sredn;

In če nasprotno, potem naredimo to spodnjo mejo:

drug niz: = sredn-
konec;

To je vse, kar bo v programu.

Analizirali bomo, kako bo v praksi videti binarna metoda. Vzemimo takšno polje: 1, 3, 5, 7, 10, 12, 18 in poiščemo številko 12 v njem.

Skupaj imamo 7 elementov, tako da bo povprečje četrte, njegova vrednost 7.

Ker je 12 več kot 7, je mogoče elemente 1,3 in 5 zavreči. Nato imamo še 4 številke, 4/2 brez ostanka pa 2. Torej bo novi srednji element 10.

Ker je 12 več kot 10, zavržemo 7. Le 10, 12 in 18 je ostalo.

Tu je srednji element že 12, to je zahtevano število. Naloga je dokončana - najdena je številka 12.