Search Binary - yek ji nimûneyên herî riyên bibînin an element di array

Gelek caran, bernamenûs, heta beginners, bi rastî ev e, ku komek ji hejmara ku divê hejmareke taybetî de bibînin li wir bi rû ne. Ev e ev collection is an array kir. Û ji bo dîtina tomar di wê de, ne şexsan de rê heye. Lê ya herî hêsan, ji wan re jî tê qebûlkirin lêgerîn binary li rastê. Çi ye, bi vê rêbazê ye? Û çawa ji bo pêkanîna lêgerîn binary? Pascal herî hêsan jîngehê ji bo rêxistina bernameyeka weha ye, wusa jî em ê ji bo xwandinê bi kar tînin.

Yekem, analîz bike, çi ji avantajên vê rêbazê ne, ew e, da ku em fêm bikin, çi ji xala ku di xebatê de ji mijarê de ye. Bi vî awayî, em ji array bi aliyê qet nebe 100000000 hêmanên, ku pêwîstî bi hinek hene. Bê guman, ev pirsgirêk bi hêsanî ji aliyê lêgerîn sade bi dîmenan, ku em bi kar tînin, di dewra wê hêmana pêwîst bi hemû kesên ku di array in our çareserkirin. Pirsgirêk ev e ku pêkanîna vê fikrê wê demê de jî, gelek bigirin. Di bernameya Pascal sade nav çend treatments, û sê xetên yên di nivîsê de sereke, hûn ê wê bala xwe ne, lê dema ku em ji bo projeyên zêdetir an kêmtir mezin bi hejmareke mezin ji çiqilên û fonksiyonên baş were, bernameya amade ne ku ji bo pir dirêj de bên barkirin dê bibe. Bi taybetî eger computer a performance lewaz e. Ji ber vê yekê, e lêgerîna binary, ku dûpatdikin dem lêgerîn qet nebe du caran li wir.

Îcar, çi prensîpa xebatê ya vê rêbazê ye? Di cih de divê bêjim ku lêgerîn binary kar e, di her array ne, di heman demê de bi tenê li ser set Rêzkirina hejmarên. Di her gavekê element navîn ya array (tê wateya hejmara element). Eger pêwîst hejmara mezintir e ji naverast, wê demê hemû ku derket, ku kêmtir ji hucreya naverast e, dikare hatibe û ji va ne li wir. Bi gotineke din, eger kêmtir ji ya navencî - di nav wan ên ku hejmara rastê, tu ne bi lêgerîn. Hingê herêma lêgerîn nû, ku hêmana yekemîn ku wê bibe elementa navîn ya tevahiya array, û roja dawîn û herî dawî îradeya hilbijêre. Hejmara navînî yên zeviyê nû dê bibe ¼ ji hemû girse, ew e ku, (hêmana dawîn + elementa navîn ya tevahiya array) / 2. Dîsa, di heman operasyonê de vegerêne - hev, bi hejmara navencî ya array. Ger nirxa target kêmtir ji ya navencî e, em red dikin di aliyê rastê de, û her weha ji bo next, heta niha ev element navîn dê xwestin ne.

Bê guman, herî baş ew e ku li mînaka çawa binivîse lêgerîn binary binêre. Pascal li vir kesek nedihatin - version e ne girîng e. Bila binivîse bernameyeke sade.

Ev nedadî yên 1 to h di bin navê "Massiv" e, a variable diyar dike ţermezarkirin kêmtir ji search, bi navê "Niz", li sînorên jor, bi navê "verh", bi navencî search term - "sredn"; û ku hejmara pêwîst - "îsk".

Bi vî awayî, pêşî em ji sînorê jêrîn û jorîn ji search range li peywirdarkirin:

Niz: = 1;
verh: = h + 1;

Hingê cycle organize ", heta ku li jêr kêmtir ji sînorê jorîn e":

Gava ku Niz destpêkirin

Di her gav, em li hev parve girse 2:

sredn: = (Niz + verh) div 2; {Bi kar div function de, ji ber ku ji ciyawaziya bê mayî}

Her dema ji review. Ji ber ku em babete ji niha ve hat dîtin, eger navîn tê xwestin e, berdidî cycle:

іf sredn = sakta paşê bişkînin;

Eger element navîn ya array zêdetir tê xwestin, piştguh aliyê çepê, ku ev e, sînora jor re ji average tayîn element:

eger Massiv [sredn]> sakta paşê verh: = sredn;

Û eger, berovajî, ew jî hat ţermezarkirin kêmtir e:

Niz din: = sredn;
dawî;

Ku hemû tiştên ku wê di bernameyê de be ye.

Werin, em bifikirin ka ev dê rêbaza binary di pratîkê de binêrin. ev array binêrin: 1, 3, 5, 7, 10, 12, 18 û ew dê bi hejmara 12 digerin.

Bi giştî em xwedî 7 hêmanên, wusa jî wê di medium çaremîn, bi nirxê 7.

Ji ber ku bêtir ji 12, 7, 1.3 û 5 hêman, em dikarin piştguh bike. Hingê em hejmara 4 rabû kiriye, 4/2 tu mayî 2. ber vê yekê, element nû dê bibe hevde 10.

Ji ber ku 12 mezintir ji 10 e, em piştguh 7. bi tenê dimîne, 10, 12 û 18.

Li vir, ew element navîn e ji niha ve 12, ev hejmara pêwîst e. Ev wezîfeyeke qediya - hejmara 12 dîtin.