Uphendlo Binary - enye yezona ndlela ilula ukufumana element in an uluhlu

Lidla badwelisi benkqubo, nkqu wabaqalayo, senze into yokuba kukho iseti yamanani, nekufuneka ukufumana inani elithile. Yiyo le ngqokelela kuthiwa ezifanayo. Kwaye ukufumana izinto kulo, kukho ezininzi ezahlukahlukeneyo. Kodwa elula uninzi lwabo nga kuthathelwa ingqalelo ukhangelo yokubini ngasekunene. Yintoni na le ndlela? Nokuba kusekwa kanjani ukufuna yokubini? Pascal okusingqongileyo ilula lokuququzelela inkqubo enjalo, ngoko siza kuyisebenzisa ukuba ukufunda.

Okokuqala, hlolisisa, yintoni iingenelo yale ndlela, ukuba uyakwazi ukuqonda ukuze thina, yintoni na le ndawana isifundo ngesihloko. Ngoko ke, masikhe babe enempi kwedimension ubuncinane 100000000 elements, ekufuneka ukufumana ezinye. Kakade ke, le ngxaki lula isonjululwe uphendlo elula yomgama, apho sisebenzisa umjikelo elinokuthelekiswa i element efunekayo nabo bonke abo kuyo ziyakhele uluhlu. Ingxaki kukuba ukuphunyezwa kwalo mbono iza kuthatha ixesha elininzi. Xa inkqubo elula Pascal zibe unyango eziliqela, kwaye imigca ezintathu kwiindinyana, uya bakuqaphele, kodwa xa kufika ukuba iiprojekthi ngaphezulu okanye ngaphantsi enkulu kunye nenani elikhulu amasebe kunye ukusebenza omhle, le nkqubo iya kuba ukulungele ukuba lolayisho ixesha elide kakhulu. Ingakumbi ukuba ikhomputha i zokusebenza. Ngoko ke, kukho uphendlo yokubini, leyo kunciphisa ixesha uphendlo ubuncinane kabini.

Ngoko ke, yintoni na umgaqo lonxibelelwano le ndlela? Ngoko nangoko ke uthi uphendlo lokubini osebenzayo akakho na uluhlu, kodwa kuphela kwiisethi ehleliweyo amanani. Kwinyathelo esithathwe isiqalelo ngasinye phakathi uluhlu (okuthetha inani element). Ukuba elifunekayo inani mkhulu ngaphezu komndilili, ngoko yonke into eseleyo, oko kukuthi ngaphantsi kwe yeseli avareji, na ezinokuyekwa, hayi ukukhangela khona. Kwelinye icala, ukuba ngaphantsi kwe-avareji - phakathi kwabo amanani ukuya ekunene, uyakwazi ukuphendla. Emva koko khetha indawo entsha search, apho Into yokuqala iya kuba element phakathi lonke uluhlu, kwaye yokugqibela kunye nentando wokugqibela. I-avareji yenani intsimi entsha iya kuba ¼ onke ceke, oko kukuthi, (i element yokugqibela + le nto phakathi lonke uluhlu) / 2. Kwakhona, umsebenzi ofanayo luyenziwa - uthelekiso ne-avareji yenani ziyakhele uluhlu. Ukuba ixabiso target lingaphantsi kwe-avareji, singayamkeli ngasekunene, kwaye kananjalo ukuba benze elandelayo, kude kube ngoku lwesi sakhi eliphakathi akayi ezinqwenelekayo.

Kakade ke, yona ilungileyo ukujonga umzekelo indlela yokubhala uphendlo yokubini. Pascal apha uya zilungele nabani - version ayibalulekanga. Masibhale inkqubo elula.

Lo uluhlu-1 ukuya h phantsi kwegama "massiv", variable ebonisa umda esezantsi uphendlo, ebizwa ngokuba "niz", nelona qondo liphezulu, ebizwa ngokuba "verh", i-avareji elithi yokukhangela - "sredn"; kwaye inani elifunekayo - "isk".

Ngoko ke, okokuqala thina kubabela umda ongentla ngaphantsi kwebanga wophendlo:

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

Emva koko ahlele umjikelo "de emazantsi lingaphantsi kwe-mda eliphezulu":

Nangona niz uqale

Kwinyathelo ngalinye, sisahlula ingxenye 2:

sredn: = (niz + verh) div 2; {Sebenzisa umsebenzi div, ngenxa yokuba umsantsa ngaphandle intsalela}

ixesha ngalinye ngokutsha. Ngenxa yokuba le nto sele kufunyenwe ukuba eliphakathi ayinqwenelayo, ziphazamise kumjikelo:

іf sredn = isk ke kuyaphula;

Ukuba element phakathi uluhlu ngaphezu oyifunayo, ulahle kwicala lasekhohlo, oko kukuthi, lo umda ongentla we computeryomndilili amisele element:

ukuba massiv [sredn]> isk ngoko verh: = sredn;

Ukuba phezu koko, yenza umda asezantsi:

niz enye into: = sredn;
iphele;

Kuko konke oko kuya kuba kule nkqubo.

Makhe siqwalasele ukuba iza kukhangeleka njani na indlela kabini practice. Qwalasela le uluhlu: 1, 3, 5, 7, 10, 12, 18 yaye oko kuya kufuna inani 12.

Xa iyonke esinayo izinto 7, kanjalo eliphakathi yesine, ixabiso-7.

Ekubeni ngaphezulu kwe-12, 7, 1.3 no-5 elements, singakwazi ulahle. Emva koko Umelwe inani 4, 4/2 akukho intsalela ngu 2. Ngoko ke, into entsha iya kuba umlinganiselo we-10.

Ukususela ngowe-12 mkhulu kuno-10, siya ulahle 7. uhlala 10, 12 no-18 kuphela.

Apha, element eliphakathi sele-12, oko kukuthi inani elifunekayo. Lo msebenzi sele sigqityiwe - inani 12 Ayifumaneki.