Binè rechèch - youn nan fason ki pi fasil jwenn yon eleman nan yon etalaj

Byen souvan, pwogramasyon, menm débutan, te fè fas ak lefèt ke gen se yon seri nimewo, ki dwe jwenn yon nimewo espesifik. Li se se koleksyon sa a yo rele yon etalaj. Men, jwenn atik nan li, gen yon myriad nan fason. Men, ka senp la pi fò nan yo dwe konsidere kòm yon rechèch binè sou bò dwat la. Ki sa ki se metòd sa a se? Ak kouman yo aplike rechèch binè? Pascal se anviwònman ki pi fasil pou òganizasyon an tout moun ki tankou yon pwogram, se konsa nou pral sèvi ak li nan etidye.

Premyèman, analize, ki sa yo avantaj ki genyen nan metòd sa a, li se konsa nou ka konprann, ki sa ki pwen an nan etid la nan sijè a. Se konsa, kite a gen yon etalaj ak yon dimansyon nan omwen 100000000 eleman, ki bezwen jwenn kèk. Natirèlman, ka pwoblèm sa a dwe fasil pou rezoud pa yon rechèch senp lineyè, nan ki nou ap itilize sik la pral konpare eleman yo egzije ak tout sa yo ki nan etalaj la. Pwoblèm lan se ke aplikasyon an nan ide sa a pral pran twòp tan. Nan yon pwogram ki senp Pascal nan plizyè tretman, ak twa liy nan tèks la prensipal yo, ou pa pral remake li, men lè nou rive nan yon plis oswa mwens gwo pwojè ki gen yon gwo kantite branch ak fonctionnalités bon, pwogram nan pral pare yo dwe chaje pou twò lontan. Espesyalman si òdinatè a se yon pèfòmans fèb. Se poutèt sa, gen yon rechèch binè, ki diminye tan rechèch omwen de fwa.

Se konsa, sa se prensip la k ap travay nan metòd sa a? Menm lè li ta dwe di ke rechèch binè travay se pa nan nenpòt etalaj, men se sèlman sou yon seri Ranje nan nimewo. Nan chak eleman mitan etap pran nan etalaj la (sa vle di ki kantite eleman an). Si sa nesesè nimewo nan pi gran pase mwayèn nan, Lè sa a, tout sa k rete, ki se mwens pase selil la mwayèn, ka abandone epi yo pa fè yon gade a. Kontrèman, si mwens pase mwayèn la - nan mitan moun ki nimewo a dwat a, ou pa ka rechèch. Lè sa a, chwazi yon zòn rechèch nouvo, kote eleman nan premye yo pral eleman nan mitan nan etalaj la an antye, ak dènye a epi yo pral an dènye. Nimewo an mwayèn nan nouvo jaden yo pral ¼ nan tout segman nan, se sa ki, (eleman ki sot pase a + eleman nan mitan nan etalaj a tout antye) / 2. Yon fwa ankò, se menm operasyon an fèt - yon konparezon ak nimewo an mwayèn nan etalaj la. Si valè a sib se mwens pase mwayèn nan, nou rejte bò dwat, epi tou li yo dwe fè pwochen, jouk jòdi a, sa a eleman mitan pa ta vle.

Natirèlman, li se pi bon fè yon gade nan yon egzanp pou konnen kijan pou ekri rechèch binè. Pascal isit la pral kostim nenpòt moun - vèsyon se pa enpòtan. Se pou yo ekri yon pwogram ki senp.

Li se yon etalaj de 1 a h anba non "masiv la", yon varyab ki endike fwontyè ki pi ba nan rechèch la, ki rele "niz", limit la anwo, ki rele "verh", tèm rechèch la mwayèn - "sredn"; ak nimewo yo egzije - "ISK".

Se konsa, premye nou bay limit la anwo ak pi ba nan rechèch la range:

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

Lè sa a, òganize sik la "jouk anba a se mwens pase limit la anwo":

Pandan ke niz kòmanse

Nan chak etap, nou divize segman an 2:

sredn: = (niz + verh) div 2; {Sèvi ak div an fonksyon, paske divize an san yo pa rès}

Chak fwa nan revizyon. Paske atik la deja te jwenn si se mwayen la vle, entèwonp sik:

іf sredn = ISK Lè sa a, kraze;

Si eleman nan mitan nan etalaj la plis pase vle, jete bò gòch, se sa ki, fwontyè a anwo nan mwayèn nan nonmen eleman:

si masiv [sredn]> ISK Lè sa a, verh: = sredn;

Men, si sou kontrè a, li fè fwontyè a pi ba:

lòt niz: = sredn;
fini;

Sa a tout sa ki pral nan pwogram nan.

Se pou nou konsidere ki jan li pral gade metòd la binè nan pratik. Konsidere sa a etalaj: 1, 3, 5, 7, 10, 12, 18 epi li pral chache nimewo a 12.

Nan total nou gen 7 eleman, se konsa yo pral medyòm a katriyèm, valè a 7.

Depi plis pase 12, 7, 1.3 ak 5 eleman, nou ka jete. Lè sa a, nou te gen nimewo a 4, 4/2 pa gen okenn rezidi se 2. Se konsa, yon eleman nouvo yo pral yon mwayèn de 10.

Depi 12 se pi gran pase 10, nou jete 7. rete sèlman 10, 12 ak 18.

Isit la, eleman nan mitan an se deja 12, li se nimewo yo egzije. Se travay sa a ranpli - nimewo 12 te jwenn.