Duumaj serĉo - unu el la plej facilaj manieroj por trovi elementon en tabelo

Tre Ofte, programistoj, eĉ komencantoj, antaŭ la fakto ke ekzistas aro de nombroj, kiu devas trovi specifan nombron. Estas ĉi tiu kolekto estas nomita tabelo. Kaj por trovi artikolojn en ĝi, ekzistas miriado de manieroj. Sed la plej simplaj el ili povas esti konsiderata duuma serĉo dekstre. Kio estas tiu metodo estas? Kaj kiel apliki duuma serĉo? Paskalo estas la plej facila medio por la organizo de tia programo, do ni uzu ĝin por studi.

Unue, analizi, kio estas la avantaĝoj de ĉi tiu metodo, ĝi estas do ni povas kompreni, kio estas la punkto en la studo de la temo. Do, ni havas tabelo kun dimensio de minimume 100000000 elementoj, kiuj devas trovi iun. Kompreneble, ĉi tiu problemo povas esti facile solvita per simpla lineara serĉo, en kiu ni uzas la ciklo komparos la postulata elemento kun ĉiuj tiuj, kiuj estas en la tabelo. La problemo estas ke la efektivigo de tiu ideo prenos tro da tempo. En simpla Paskalo programon en pluraj traktadoj, kaj tri linioj de la ĉefa teksto, vi ne rimarkos ĝin, sed kiam ni venis al pli malpli grandaj projektoj kun granda nombro da branĉoj kaj bona funcionalidad, la programo estos preta por esti ŝarĝita por tro longa. Precipe se la komputilo estas malforta elfaro. Sekve, estas duuma serĉo, kiu reduktas serĉo tempo minimume dufoje.

Do, kio estas la laborista principo de tiu metodo? Tuj ĝi devus diri ke duuma serĉo laboras ne estas en ajna tabelo, sed nur sur ordo aro de nombroj. Ĉe ĉiu paŝo prenita mezo elemento de la array (signifas la numeron de la elemento). Se la postulata nombro estas pli granda ol la ordinara, do ĉiuj restintoj, kiuj estas malpli ol la mezumo ĉelo, povas esti forĵetita kaj ne rigardi tie. Male, se malpli ol la mezumo - inter tiuj nombroj dekstren, vi ne povas serĉi. Tiam elektu novan serĉon areon, kie la unua elemento estos la mezo elemento de la tuta tabelo, kaj la lasta kaj la lasta volo. La averaĝa nombro de novaj kampo estos ¼ de la tuta segmento, kiu estas, (la lasta elemento + la mezo elemento de la tuta tabelo) / 2. Denove, la sama operacio estas farita - komparon kun averaĝa nombro de la tabelo. Se la celo valoro estas malpli ol la mezumo, ni malakceptas la dekstra flanko, kaj ankaŭ fari poste, ĝis nun ĉi tiu mezo elemento ne deziris.

Kompreneble, ĝi estas plej bone rigardu ekzemplon de kiel skribi duuma serĉo. Pascal tie deca iu - versio ne gravas. Ni skribu simplan programon.

Ĝi estas tabelo de 1 al h sub la nomo "massiv", variablo indikante la suba limo de la serĉo, nomata "niz", la supra limo, nomita "verh", la mezumo serĉvortoj - "sredn"; kaj la postulata nombro - "ISK".

Do, unue ni atribui la supra kaj suba limo de la gamo de serĉo:

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

Tiam organizi la ciklo "ĝis la fundo estas malpli ol la supra limo":

Dum niz komenci

Ĉe ĉiu paŝo, ni dividu la segmento 2:

sredn: = (niz + verh) div 2; {Uzu la funkcion div, ĉar la divido sen cetero}

Ĉiu tempo de revizio. Ĉar la elemento jam estis trovita ke la meza estas dezirata, interrompi ciklo:

іf sredn = ISK tiam rompu;

Se la meza elemento de la tabelo pli ol dezirata, forĵeti la maldekstra flanko, tio estas, la supra limo de la mezumo nomumi elementon:

se massiv [sredn]> ISK tiam verh: = sredn;

Se male, ĝi faras la pli malalta limo:

alie niz: = sredn;
fini;

Jen ĉio, ke estos en la programo.

Ni konsideru kiel aspektos la duuma metodo en praktiko. Konsideru ĉi tabelo: 1, 3, 5, 7, 10, 12, 18 kaj ĝi serĉos la nombro 12.

Entute ni havas 7 elementoj, tiam la kvara meza, la valoro 7.

Ekde pli ol 12, 7, 1,3 kaj 5 elementoj, ni povas forĵeti. Tiam ni havas la nombro 4, 4/2 neniu restaĵo estas 2. Do, nova elemento estos mezumo de 10.

Ekde la 12 estas pli granda ol 10, ni forĵetos 7. restas nur 10, 12 kaj 18.

Ĉi tie, la mezo elemento estas jam 12, estas la postulata kvanto. Tiu tasko estas kompletigita - numero 12 trovita.