Binary paghahanap - isa sa mga pinakamadaling paraan upang makahanap ng isang elemento sa isang array

Medyo madalas, programmer, kahit sa mga nagsisimula, nahaharap sa ang katunayan na ang doon ay isang hanay ng mga numero, na kung saan ay dapat mahanap ang isang tiyak na numero. Ito ay koleksyon na ito ay tinatawag na isang array. At upang mahanap ang mga item sa loob nito, may isang napakaraming bilang ng mga paraan. Ngunit ang pinaka-simple ng mga ito ay maaaring ituring na isang binary paghahanap sa kanan. Ano ang pamamaraan na ito ay? At kung paano ipatupad binary paghahanap? Pascal ay ang pinakamadaling na kapaligiran para sa samahan ng naturang programa, kaya ipapakita namin gamitin ito upang mag-aral.

Una, pag-aralan, kung ano ang mga pakinabang ng ang paraan na ito, ito ay upang maaari naming maintindihan, ano ay ang punto sa pag-aaral ng paksa. Kaya, sabihin magkaroon ng isang array na may sukat na hindi bababa sa 100000000 mga elemento, na kailangan upang mahanap ang ilang. Of course, ang problemang ito ay madaling malutas sa pamamagitan ng isang simpleng linear paghahanap, na kung saan ginagamit namin ang mga cycle ay ihambing ang mga kinakailangang mga elemento na may lahat ng mga na nasa array. Ang problema ay na ang pagpapatupad ng mga ideya na ito ay magdadala ng masyadong maraming oras. Sa isang simpleng Pascal program sa ilang mga paggamot, at tatlong linya sa mga pangunahing teksto, hindi mo mapansin ito, ngunit kapag dumating namin sa isang higit pa o mas malaking proyekto na may isang malaking bilang ng mga sanga at mabuting pag-andar, ang programa ay handa na upang i-load para sa masyadong mahaba. Lalo na kung ang computer ay isang mahinang pagganap. Samakatuwid, mayroong isang binary paghahanap, na binabawasan ang time na paghahanap ng hindi bababa sa dalawang beses.

Kaya, ano ay ang nagtatrabaho prinsipyo ng ang paraan na ito? Kaagad dapat itong sabihin na binary paghahanap ay gumagana ay hindi sa anumang array, ngunit lamang sa isang pinagsunod-sunod na hanay ng mga numero. Sa bawat hakbang na kinuha gitnang elemento ng array (ibig sabihin ang bilang ng mga elemento). Kung ang mga kinakailangang mga numero ay mas malaki kaysa sa average na, at pagkatapos ay lahat na ay kaliwa, iyon ay mas mababa kaysa sa average na cell, ay maaaring itinapon at hindi upang tumingin doon. Sa kabaligtaran, kung mas mababa kaysa sa average na - kabilang sa mga numero sa kanan, hindi ka maaaring maghanap. Pagkatapos ay piliin ang isang bagong search area kung saan ang unang elemento ay ang gitnang elemento ng buong array, at ang huling at ang huling kalooban. Ang average na bilang ng mga bagong larangan ay ¼ ng lahat ng mga segment, iyon ay, (ang huling elemento + ang gitnang elemento ng buong array) / 2. Muli, ang parehong operasyon ay ginanap - isang paghahambing sa ang average na bilang ng array. Kung ang target na halaga ay mas mababa kaysa sa average, tanggihan namin sa kanang bahagi, at din ang susunod na gagawin, hanggang ngayon ito gitnang elemento ay hindi ninanais.

Of course, ito ay pinakamahusay upang tumingin sa isang halimbawa ng kung paano sumulat ng binary paghahanap. Pascal dito ay angkop sa kahit sino - bersyon ay hindi mahalaga. magsulat ng isang simpleng programa Hayaan.

Ito ay isang hanay ng mga 1 hanggang h ilalim ng pangalang "massiv", isang variable na nagpapahiwatig ng mas mababang mga hangganan ng paghahanap, na tinatawag na "niz", ang mataas na limitasyon, na tinatawag na "verh", ang average na terminong ginamit sa paghahanap - "sredn"; at ang mga kinakailangang bilang - "isk".

Kaya, una magtalaga namin ang upper at lower limitasyon ng saklaw ng paghahanap:

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

Pagkatapos ay ayusin ang cycle "hanggang ibaba ay mas mababa kaysa sa itaas na limitasyon":

Habang niz magsimula

Sa bawat hakbang, hinati namin ang segment 2:

sredn: = (niz + verh) div 2; {Gamitin ang function na div, dahil ang hatiin nang walang natitira}

Sa bawat oras ng pagsusuri. Dahil ang mga item ay na-natagpuan kung ang medium ay ninanais, aabalahin ikot:

kung ang sredn = isk pagkatapos ay masira;

Kung ang gitnang elemento ng array higit sa ninanais, itapon ang kaliwang bahagi, iyon ay, sa itaas na hangganan ng average humirang ng sangkap na:

kung massiv [sredn]> isk pagkatapos ay verh: = sredn;

At kung sa salungat, ito ay gumagawa ng mga mas mababang mga hangganan:

iba niz: = sredn;
end;

Iyon lang ang na magiging sa programa.

Tingnan natin kung paano ito ay tumingin sa binary pamamaraan sa kasanayan. Isaalang-alang ang array: 1, 3, 5, 7, 10, 12, 18 at ito ay humingi ng bilang 12.

Sa kabuuan mayroon kaming 7 elemento, sa gayon ay ang ika-apat na medium, ang halaga 7.

Dahil higit sa 12, 7, 1.3 at 5 elemento, maaari naming itapon. Pagkatapos namin nakuha ang number 4, 4/2 walang nalalabi ay 2. Kaya, ang isang bagong elemento ay magiging isang average ng 10.

Since 12 ay mas malaki kaysa sa 10, itapon namin 7. nananatiling lamang 10, 12 at 18.

Dito, ang gitnang elemento ay naka-12, ito ay ang mga kinakailangang numero. Ang gawain na ito ay nakumpleto - number 12 natagpuan.