Binary search - moja ya njia rahisi ya kupata kipengele katika safu

Mara nyingi, programmers, hata wanaoanza, wanakabiliwa na ukweli kwamba kuna seti ya namba, ambayo lazima kupata idadi maalum. Ni mkusanyiko hii inaitwa mkusanyiko. Na kupata vitu ndani yake, kuna elfu kumi ya njia. Lakini rahisi wengi wao inaweza kuchukuliwa search binary upande wa kulia. Ni nini njia hii ni? Na jinsi ya kutekeleza search binary? Pascal ni mazingira rahisi kwa ajili ya shirika la mpango huo, hivyo tutatumia ni kusoma.

Kwanza, uchambuzi, ni faida ya njia hii, ni ili tuweze kuelewa, je, ni hatua katika utafiti wa mada. Hivyo, hebu kuwa na mkusanyiko na mwelekeo wa mambo angalau 100000000, ambayo unahitaji kupata baadhi. Bila shaka, tatizo hili inaweza kuwa rahisi kutatuliwa kwa utafutaji rahisi linear, ambapo tunatumia mzunguko itakuwa kulinganisha kipengele required kwa kuwa ni katika safu ya wale wote. Tatizo ni kwamba utekelezaji wa wazo hili itachukua muda sana. Katika mpango rahisi Pascal katika matibabu kadhaa, na mistari mitatu ya maandishi kuu, huwezi taarifa hiyo, lakini wakati sisi kuja miradi zaidi au chini ya kubwa na idadi kubwa ya matawi na utendaji mzuri, mpango itakuwa tayari kubeba kwa muda mrefu sana. Hasa kama kompyuta ni utendaji dhaifu. Kwa hiyo, kuna search binary, ambayo hupunguza search wakati angalau mara mbili.

Hivyo, ni nini kanuni ya kazi ya njia hii? Mara ni lazima kusema kwamba search binary kazi ni si katika safu yoyote, lakini tu kwa kuweka sorted ya namba. Katika kila hatua zilizochukuliwa kati kipengele cha safu (maana idadi ya kipengele). Kama required idadi ni kubwa zaidi kuliko wastani, kisha wote ni wa kushoto, ambayo ni chini ya kiini wastani, inaweza kuondolewa na si kwa kuangalia huko. Kwa upande mwingine, ikiwa chini ya wastani - kati namba hizo kwa haki, huwezi kutafuta. Kisha chagua kutafuta eneo jipya, ambapo kipengele kwanza itakuwa kipengele katikati ya safu nzima, na ya mwisho na mapenzi ya mwisho. wastani wa idadi ya uwanja mpya itakuwa ¼ ya sehemu zote, yaani, (kipengele cha mwisho + kipengele katikati ya safu nzima) / 2. Kwa mara nyingine, operesheni hiyo ni kazi - kulinganisha na wastani wa idadi ya mkusanyiko. Kama lengo thamani ni chini ya wastani, sisi kukataa upande wa kulia, na pia kufanya ijayo, mpaka sasa kipengele hiki katikati hakutaka taka.

Bila shaka, ni bora kuangalia mfano wa jinsi ya kuandika search binary. Pascal hapa kukidhi mtu - toleo si muhimu. Hebu kuandika mpango rahisi.

Ni safu ya 1 hadi h chini ya jina "Massiv", variable kuonyesha mipaka ya chini ya utafutaji, inayoitwa "niz", ukomo wa juu, inayoitwa "verh", wastani wa muda wa kutafuta - "sredn"; na idadi ya mahitaji - "ISK".

Kwa hiyo, kwanza sisi hawawajui juu na chini ya kikomo ya utafutaji mbalimbali:

niz: = 1;
verh: = h + 1;

Kisha kuandaa mzunguko "mpaka chini ni chini ya kikomo ya juu":

Wakati niz kuanza

Katika kila hatua, sisi kugawanya sehemu ya 2:

sredn: = (niz + verh) div 2; {Matumizi ya kazi div, kwa sababu mgawanyiko bila salio}

Kila wakati wa mapitio. Kwa sababu bidhaa tayari kupatikana ikiwa kati ni taka, kukatiza mzunguko:

іf sredn = ISK kisha kuvunja;

Kama kipengele katikati ya safu zaidi ya taka, kutupa upande wa kushoto, yaani, mpaka wa juu wa kila kuteua kipengele:

kama Massiv [sredn]> ISK kisha verh: = sredn;

Na kama kinyume chake, inafanya mpaka chini:

mwingine niz: = sredn;
mwisho,

Hayo ni yote hiyo ni katika mpango.

Hebu fikiria jinsi gani itakuwa kuangalia njia binary katika mazoezi. Fikiria safu hii: 1, 3, 5, 7, 10, 12, 18 na itakuwa kutafuta namba 12.

Kwa ujumla tuna mambo 7, ndivyo kati ya nne, thamani 7.

Kwa kuwa zaidi ya 12, 7, 1.3 na 5 mambo, tunaweza kuondokana na. Kisha sisi tumepewa namba 4, 4/2 mabaki ni 2. Hivyo, kipengele mpya itakuwa wastani wa 10.

Tangu 12 ni zaidi ya 10, sisi kutupa 7. bado tu 10, 12 na 18.

Hapa, kipengele katikati tayari 12, ni idadi inayotakiwa. Kazi hii imekamilika - Idadi 12 kupatikana.