Suesuega Binary - o se tasi o auala sili ona faigofie e maua ai se elemene i se autau

Le tele o taimi, polokalame, e tusa lava e amataina, feagai ma le mea moni e faapea o loo i ai se seti o fuainumera, lea e tatau ona maua se numera faapitoa. O lenei aoina e valaauina se autau. Ma e maua mea i ai, o loo i ai se anoanoai o auala. Ae o le faigofie o le tele o latou e mafai ona manatu i se suesuega binary i le itu taumatau. O le a lenei auala o? Ma le auala e faatino ai suesuega binary? Pascal o le siosiomaga sili ona faigofie mo le faatulagaina o se polokalame, o lea o le a tatou faaaogaina e suesue ai.

Muamua, faavasega, o le a o le tulaga lelei o lenei auala, e faapea e mafai ona tatou malamalama i ai, o le a le taimi i le suesueina o le autu. O lea, ia a maua se autau i se tulaga o le le itiiti ifo i 100000000 elemene, lea e manaomia e maua ai nisi. O le mea moni, e mafai ona faigofie ona foia lenei faafitauli e ala i se sailiga linear faigofie, o loo tatou faaaogaina le faataamilosaga faatusaina le elemene manaomia ma i latou uma o loo i le autau. O le faafitauli e faapea o le a umi se taimi tele i le faatinoina o lenei manatu. I se polokalama Pascal faigofie i ni togafitiga, ma le tolu o laina o le mataupu autu, o le ae matauina ai, ae pe a tatou oo mai i se galuega faatino e sili atu pe itiiti tele ma se vaega tele o paranesi ma functionality lelei, o le a saunia le polokalama e ona utaina mo umi. Aemaise lava pe afai o le komepiuta o se faatinoga vaivai. O le mea lea, o loo i ai se suesuega binary, lea e faaitiitia ai le taimi e sueina le itiiti ifo i le faalua.

O lea, o le a le mataupu faavae o galuega o le auala lenei? Le taimi lava lena e tatau ona fai e galue binary suesuega e le i so o se autau, ae na i luga o se seti faavasegaina o numera. I taitasi elemene ogatotonu faia laasaga o le autau (o lona uiga o le aofai o le elemene). Afai e le manaomia e sili atu le aofai nai lo le averesi, ona uma ua totoe, e itiiti ifo nai lo o le sela averesi, e mafai ona tiai nei ma le toe vaai i ai. Itu, afai e itiiti ifo nai lo le averesi - i totonu oi latou numera i le itu taumatau, e le mafai ona suesue. Ona filifili se eria suesuega fou, pe afai o le elemene muamua o le a le elemene ogatotonu o le autau atoa, ma o le mulimuli ma le finagalo mulimuli. O le fua tutusa o fanua fou o le a avea ¼ o le vaega uma, e, (o le elemene mulimuli + le elemene ogatotonu o le autau atoa) / 2. O lenei foi, o loo faatinoina le galuega lava lea e tasi - a faatusatusa atu i le numera o le averesi o le autau. Afai o le sini taua e itiiti ifo nai lo le averesi, tatou te teena le itu taumatau, ma foi e faia e sosoo ai, seia oo i le taimi nei o le a le manao lenei elemene ogatotonu.

O le mea moni, e sili atu le vaai i se faataitaiga o le auala e tusi sailiga binary. a fetaui iinei Pascal se tasi - e le o taua lomiga. Ia o le tusi se polokalama faigofie.

O se autau o le 1 i h lalo o le igoa "massiv", o se ma liuliuina faailoa le tuaoi i lalo o le suesuega, e taʻua "niz", o le tapulaa pito i luga, e taʻua "verh", le averesi suesuega vaitaimi - "sredn"; ma le aofaiga manaomia - "isk".

O lea, muamua tatou tofi o le tapulaa i luga ma lalo o le sailiga tele:

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

Ona faatulaga le taamilosaga "seia e itiiti ifo i le pito i lalo nai lo le tapulaa pito i luga":

A niz amata

I laasaga taitasi, tatou te vaevaeina le vaega 2:

sredn: = (niz + verh) div 2; {Faaaoga le galuega tauave div, aua o le vaevae aunoa totoe}

O taimi uma lava o le toe iloiloga. Talu ai ona ua uma ona maua le mea pe afai ua finagalo i ai le auala, faalavelave taamilosaga:

іf sredn = isk lea solia;

Afai o le elemene ogatotonu o le autau sili atu nai lo e manaomia, tuulafoai i le itu tauagavale, o, o le tuaoi i luga o le averesi tofia elemene:

pe afai massiv [sredn]> isk lea verh: = sredn;

Ma afai i luga o le ese mai ai, e faia e le tuaoi i lalo:

niz isi: = sredn;
muta;

O le uma o le a i ai i le polokalama.

Ia tatou mafaufau i le auala o le a vaai i le auala binary i faiga. Seʻi manatu i lenei autau: 1, 3, 5, 7, 10, 12, 18 ma o le a saili atu i le numera 12.

I le aofaiga tatou 7 elemene, lea o le a le auala lona fa, o le taua 7.

Talu mai le silia i le 12, 7, 1.3 ma le 5 elemene, e mafai ona tatou lafoaia. Ona ua tatou maua le numera 4, 4/2 leai se toega e 2. O lea la, o le a se elemene fou ai tusa o le 10.

Talu ai e sili 12 i lo le 10, ua tatou lafoaia 7. tumau pea na o le 10, 12 ma le 18.

Iinei, o le elemene ogatotonu ua uma ona 12, o le numera manaomia. O lenei galuega ua maea - numera 12 maua.