Usesho Binary - enye yezindlela elula yokuthola i-elementi array

Kaningi, program, ngisho Wabasaqalayo, wabhekana neqiniso lokuthi kukhona iqoqo izinombolo, okumele ukuthola inombolo ethize. Kuyinto leli qoqo ibizwa ngokuthi yi-array. Futhi ukuthola izinto kuwo, kukhona inqwaba izindlela. Kodwa elula iningi labo likwazi kubhekwe usesho kanambambili ngakwesokudla. Kuyini lokhu ndlela? Futhi ukuthi kusetshenziswe kanjani search kanambambili? Pascal imvelo elula lenhlangano kwezinhlelo ezinjalo, ngakho ke sizosebenzisa ke ukufunda.

Okokuqala, hlaziya, iziphi izinzuzo le ndlela, kuba ukuze sizwisise, liyini iphuzu ekuhloleni isihloko. Ngakho, ake abe array ne isici okungenani 100000000 izakhi, okuyinto udinga ukuthola abanye. Yiqiniso, le nkinga kungenziwa kalula ixazululwe usesho komugqa elula, lapho sisebenzisa umjikelezo ngeke uqhathanise elementi adingekayo nazo zonke lezo amalungu afanayo. Inkinga wukuthi ukusebenza kwalesi umqondo kuzothatha isikhathi esiningi. Ngo uhlelo elula Pascal ku ukwelashwa eziningana, futhi obuthathu umbhalo omkhulu, wena ngeke uphawule, kodwa lapho sifike amaphrojekthi ucishe enkulu nge inqwaba amagatsha nokusebenza okuhle, uhlelo izolungela ukulayishwa isikhathi eside kakhulu. Ikakhulukazi uma ikhompyutha ukusebenza ababuthakathaka. Ngakho-ke, kukhona search kanambambili, okuyinto kunciphisa search isikhathi okungenani kabili.

Ngakho, liyini isimiso ukusebenza le ndlela? Ngokushesha kufanele bathi search kanambambili usebenza alikho iyiphi afanayo, kodwa kuphela iqoqo tabuye izinombolo. Ngezinye isinyathelo esithathwe ngamunye isici phakathi afanayo (okusho isibalo element). Uma kudingeka inombolo mkhulu kunezinhliziyo isilinganiso ke konke ishiywa, okungukuthi esingaphansi iseli Ngokwesilinganiso, kungenziwa alahlwe futhi bangabheki khona. Ngakolunye uhlangothi, uma engaphansi kwesilinganiso - among labo izinombolo kuya kwesokudla, awukwazi ukusesha. Bese ukhethe indawo entsha search, lapho element lokuqala kuyoba isici phakathi wonke amalungu afanayo, abokugcina babe kanye incwadi yefa. Inani eliyisilinganiso ensimini entsha kuyoba ¼ we zonke ingxenye, okungukuthi, (kungxenye yokugcina + element phakathi wonke amalungu afanayo) / 2. Nalapha futhi, ukusebenza efanayo wenziwa - ukuqhathanisa nenani isilinganiso afanayo. Uma ukubaluleka target ingaphansi Ngokwesilinganiso, siyakulahla ngakwesokunene, futhi kumele wenzeni ngokulandelayo, kuze kube manje lesi sici phakathi ngeke oyifunayo.

Yiqiniso, kungcono kakhulu ukunquma ukuthi sibheke isibonelo sendlela ukubhala search kanambambili. Pascal lapha ngeke ivumelane ubani - version ayibalulekile. Asibhale uhlelo elula.

Kuyinto uxhaxha 1 kuya h ngaphansi kwegama "massiv", kwenombolo ekhombisa umngcele engezansi yokusesha, ngokuthi "niz", mkhawulo, ngokuthi "verh", isilinganiso itemu - "sredn"; futhi inani elidingekayo - "isk".

Ngakho, kuqala thina nika umkhawulo engenhla nengezansi yokusesha ububanzi:

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

Khona-ke ukuhlela umjikelezo "kuze phansi ingaphansi mkhawulo":

Nakuba niz uqale

Kuleso naleso sinyathelo, thina ukwehlukana ingxenye 2:

sredn: = (niz + verh) div 2; {Sebenzisa div umsebenzi, ngoba ukuhlukana ngaphandle okusele}

Njalo ka isibuyekezo. Ngoba entweni useke watholakala uma medium oyifunayo, uphazamisa umjikelezo:

іf sredn = isk ke aphule;

Uma isici phakathi afanayo ezingaphezu kuka oyifunayo, ukulahla ohlangothini lwesobunxele, okungukuthi, umngcele engenhla isilinganiso ukhethe ingxenye:

uma massiv [sredn]> isk ke verh: = sredn;

Futhi uma kunalokho, kwenza umngcele engezansi:

niz okunye: = sredn;
ukuqeda;

Yilokho konke kuyoba ohlelweni.

Ake sicabangele indlela uyobheka indlela kanambambili practice. Cabangela lokhu afanayo: 1, 3, 5, 7, 10, 12, 18 futhi bayofuna inombolo 12.

Sekukonke esinalo izakhi 7, kanjalo naphakathi wesine, ukubaluleka 7.

Njengoba ezingaphezu kuka-12, 7, 1.3 no-5 izakhi, singakwazi ukulahla. Khona-ke sinezinto inombolo 4, 4/2 akukho zinsalela kuyinto 2. Ngakho, isici esisha kuyoba isilinganiso sama-10.

Njengoba 12 mkhulu kunezinhliziyo 10, silahle 7. uhlala 10, 12 nengu-18 kuphela.

Lapha, i-elementi phakathi isivele 12, kuba inani elidingekayo. Lo msebenzi usuphothuliwe - inombolo 12 ezitholakele.