Binary chwilio - un o'r ffyrdd hawsaf o ddod o hyd i elfen mewn amrywiaeth

Yn aml iawn, rhaglenwyr, hyd yn oed dechreuwyr, yn wyneb y ffaith bod yna set o rifau, y mae'n rhaid iddo ddod o hyd i nifer penodol. Mae'n gelwir y casgliad hwn yn arae. Ac i ddod o hyd i eitemau ynddo, mae myrdd o ffyrdd. Ond gall y syml y rhan fwyaf ohonynt yn cael eu hystyried chwiliad deuaidd ar y dde. Beth yw dull hwn yw? A sut i weithredu chwiliad deuaidd? Pascal yw'r amgylchedd hawsaf ar gyfer trefnu rhaglen o'r fath, felly byddwn yn ei ddefnyddio i astudio.

Yn gyntaf, dadansoddi, beth yw manteision y dull hwn, mae'n er mwyn i ni ddeall, beth yw'r pwynt yn yr astudiaeth o'r pwnc. Felly, gadewch i ni gael amrywiaeth gyda dimensiwn o leiaf 100000000 elfen, y mae angen i ddod o hyd. Wrth gwrs, gall y broblem hon ei datrys yn hawdd gan chwiliad llinol syml, yr ydym yn defnyddio'r cylch yn cymharu yr elfen angenrheidiol gyda phawb sydd yn y casgliad. Y broblem yw y bydd y syniad hwn ar waith yn cymryd gormod o amser. Mewn rhaglen Pascal syml i mewn i nifer o driniaethau, ac dair llinell o'r prif destun, ni fyddwch yn sylwi arno, ond pan fyddwn yn dod i fwy neu lai fawr o brosiectau gyda nifer fawr o ganghennau ac ymarferoldeb da, bydd y rhaglen yn barod i gael eu llwytho yn rhy hir. Yn enwedig os y cyfrifiadur yn berfformiad gwan. Felly, mae yna chwiliad deuaidd, sy'n lleihau amser chwilio o leiaf ddwywaith.

Felly, beth yw'r egwyddor gweithio y dull hwn? Yn syth dylai ddweud bod chwilio deuaidd yn gweithio nad yw mewn unrhyw array, ond dim ond ar set ddidoli o rifau. Ar bob cam a gymerir elfen ganol y rhesi (sy'n golygu nifer yr elfen). Os yw'r gofynnol rhif yn fwy na'r cyfartaledd, yna i gyd sydd ar ôl, sy'n llai na'r cyfartaledd gell, yn gallu cael eu taflu ac nid i edrych yno. I'r gwrthwyneb, os yw'n llai na'r cyfartaledd - ymhlith y niferoedd hynny ar y dde, ni allwch chwilio. Yna dewiswch ardal chwilio newydd, lle bydd yr elfen gyntaf yn yr elfen ganol y rhesi cyfan, a'r olaf a'r ewyllys diwethaf. Bydd y nifer cyfartalog o cae newydd yn ¼ o'r holl segment, hynny yw, (yr elfen olaf + elfen ganol y rhesi cyfan) / 2. Unwaith eto, yr un llawdriniaeth yn cael ei pherfformio - cymhariaeth â nifer cyfartalog y rhesi. Os yw gwerth targed yn llai na'r cyfartaledd, byddwn yn gwrthod yr ochr dde, a hefyd i wneud nesaf, hyd yn hyn ni fyddai hyn yn elfen canol a ddymunir.

Wrth gwrs, mae'n well edrych ar enghraifft o sut i ysgrifennu chwilio deuaidd. Pascal yma yn addas i unrhyw un - nid fersiwn yn bwysig. Gadewch i ysgrifennu rhaglen syml.

Mae'n amrywiaeth o 1 i h dan yr enw "massiv", newidyn sy'n dangos ffin isaf y chwilio, a elwir yn "niz", y terfyn uchaf, a elwir yn "verh", y cyfartaledd term chwilio - "sredn"; a'r nifer gofynnol - "ISK".

Felly, yn gyntaf rydym yn aseinio y terfyn uchaf ac isaf y chwiliad ystod:

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

Yna trefnu cylch "nes bod y gwaelod yn llai na'r terfyn uchaf":

Tra niz dechrau

Ar bob cam, rydym yn rhannu'r segment 2:

sredn: = (niz + verh) div 2; {Defnyddiwch y div swyddogaeth, gan fod y rhaniad heb gweddill}

Bob adeg yr adolygiad. Oherwydd bod yr eitem wedi cael ei ddarganfod yn barod os cyfrwng dymunir, torri ar draws cylch:

іf sredn = ISK yna torri;

Os yw'r elfen ganol y rhesi yn fwy na ddymunir, taflu yr ochr chwith, hynny yw, mae ffin uchaf y cyfartaledd benodi elfen:

os massiv [sredn]> ISK yna verh: = sredn;

Ac os i'r gwrthwyneb, mae'n gwneud y ffin isaf:

arall niz: = sredn;
ben;

Dyna i gyd a fydd yn y rhaglen.

Gadewch i ni ystyried sut y bydd yn edrych y dull deuaidd yn ymarferol. Ystyriwch amrywiaeth hon: 1, 3, 5, 7, 10, 12, 18 a bydd yn ceisio rhif 12.

At ei gennym 7 elfen, felly hefyd y bydd y pedwerydd canolig, mae'r gwerth 7.

Ers mwy na 12, 7, 1.3 a 5 elfen, gallwn daflu. Yna rydym wedi cael y rhif 4, 4/2 dim gweddillion yn 2. Felly, bydd elfen newydd yn gyfartaledd o 10.

Ers 12 yn fwy na 10, rydym yn taflu 7. parhau i fod dim ond 10, 12 a 18.

Yma, yr elfen canol eisoes 12, ei fod yn y nifer gofynnol. Mae'r dasg hon yn cael ei gwblhau - rhif 12 dod o hyd.