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 je binarno iskanje. Kakšna je metoda? In kako izvajati binarno iskanje? Pascal je najpreprostejše okolje za organizacijo takega programa, zato ga bomo uporabili za študij.

Najprej bomo analizirali, kakšne so prednosti te metode, tako da lahko razumemo, Kakšen je smisel 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šimo z enostavnim linearnim iskanjem, v katerem uporabimo zanko za primerjavo želenega elementa z vsemi tistimi, ki obstajajo v matriki. Težava je, da bo izvajanje te ideje trajalo preveč časa. V preprostem programu Pascal za več postopkov in s tremi vrsticami glavnega besedila tega ne boste opazili, toda če začnete z večjo ali manj velikimi projekti z veliko razvejanjem in dobro funkcionalnostjo, bo dokončan program naložen predolgo. Še posebej, če ima računalnik slabe rezultate. Zato obstaja binarno iskanje, ki zmanjša čas iskanja vsaj za dvakrat.

Torej, kakšno je načelo te metode? Takoj je smiselno reči, da binarno iskanje ne deluje v nobeni matriki, temveč samo v razvrščenem nizu številk. Na vsakem naslednjem koraku se vzame povprečni element matrike (ki se nanaša na številko elementa). Če je želeno število večje od povprečja, lahko vse, kar je na levi, to je manj kot povprečni element, lahko zavržete in ne iščete tam. Nasprotno, če je manjše od povprečja, med številkami na desni, jih ne morete iskati. Nato bomo izbrali novo območje iskanja, kjer bo srednji element celotnega polja prvi element, zadnji pa bo zadnji. Povprečna številka novega območja bo ¼ celotnega segmenta, to je (zadnji element + povprečni 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 najboljši način za prikaz primera, kako napisati binarno iskanje. Pascal tukaj je primeren za vsakogar - različica ni pomembna. Napišite preprost program.

Imela bo niz od 1 do h, imenovan "masiv", spremenljivka, ki označuje spodnjo mejo iskanja, imenovano "niz", zgornja oznaka z imenom "verh", srednji element iskanja je "sredn"; In zahtevano število je "isk".

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

Niz: = 1;
Verh: = h + 1;

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

Medtem ko niz Začni

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 želeni element že ugotovljen:

Íf sredn = isk nato odmor;

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

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

In če nasprotno, potem naredimo to spodnjo mejo:

Drugi niz: = sredn;
Konec;

To je vse, kar bo v programu.

Analiziramo, kako binarna metoda bo v praksi videti. Vzemite takšno polje: 1, 3, 5, 7, 10, 12, 18 in poiščite številko 12 v njem.

Skupaj imamo 7 elementov, tako da bo povprečje četrto, 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 so ostali.

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