Melko usein ohjelmoijat, jopa aloittelijat,edessä tosiasia, että on olemassa joukko numeroita, joista sinun täytyy löytää tietty numero. Tätä kokoelmaa kutsutaan matriisiksi. Ja löytääksesi halutun elementin siitä, on olemassa monia erilaisia tapoja. Mutta yksinkertaisinta niistä voidaan perustellusti pitää binaarisena hauna. Mikä on annettu menetelmä? Ja kuinka toteuttaa binaarihaku? Pascal on helpoin ympäristö tällaisen ohjelman järjestämiseen, joten käytämme sitä opiskeluun.
Ensinnäkin tarkastellaan tämän menetelmän etuja, koska voimme ymmärtää
Joten mikä on tämän periaatemenetelmä? On syytä todeta heti, että binaarihaku ei toimi millään taulukolla, vaan vain lajitelluilla numeroilla. Jokaisessa seuraavassa vaiheessa otetaan taulukon keskielementti (tarkoitetaan elementin numerolla). Jos haluttu luku on keskiarvoa suurempi, niin kaikki vasemmalla oleva eli pienempi kuin keskimmäinen elementti voidaan hylätä eikä etsiä sieltä. Toisaalta, jos keskimääräistä vähemmän - oikealla olevista numeroista ei voi tehdä hakuja. Seuraavaksi valitsemme uuden hakualueen, jossa ensimmäinen elementti on koko taulukon keskielementti ja viimeinen pysyy viimeisenä. Uuden alueen keskimääräinen lukumäärä on ¼ koko segmentistä, eli (viimeinen elementti + koko taulukon keskielementti) / 2. Jälleen sama toimenpide suoritetaan - vertailu taulukon keskimääräiseen lukumäärään. Jos haluttu arvo on pienempi kuin keskimääräinen, hylkäämme oikean puolen ja teemme samalla edelleen, kunnes tämä keskielementti löytyy.
Tietysti on parasta tarkastella esimerkkiä siitä, kuinka binaarinen haku kirjoitetaan. Pascal sopii kaikille täällä - versio ei ole tärkeä. Kirjoitetaan yksinkertainen ohjelma.
Sillä on taulukko 1 - h, jota kutsutaan"massiv", muuttuja, joka merkitsee haun alarajaa nimeltään "niz", ylärajaa kutsutaan "verh", haun keskiosa on "sredn"; ja etsimäsi numero isk.
Joten ensin määritämme hakuvälin ylä- ja alarajat:
pohja: = 1;
verh: = h + 1;
Sitten järjestämme jakson "kun alempi on alle ylärajan":
Vaikka niz
Jaa kussakin vaiheessa segmentti 2: lla:
sredn: = (niz + verh) div 2; {käytämme div-funktiota, koska jaamme ilman jäännöstä}
Joka kerta kun tarkistamme. Jos keskiarvo on haluttu, keskeytämme jakson, koska haluttu elementti on jo löytynyt:
jos sredn = isk, murta sitten;
Jos ryhmän keskielementti on haluttua suurempi, hylkäämme vasemman sivun, ts. Keskimmäisen elementin osoitamme ylärajaan:
jos array yusrednshch> oikeusjuttu alkuun: = keskimääräinen;
Ja jos päinvastoin, niin teemme siitä alarajan:
muu pohja: = keskimääräinen;
end;
Se on kaikki mitä ohjelmassa on.
Katsotaan kuinka binaarimenetelmä näyttää käytännössä. Otetaanpa tällainen taulukko: 1, 3, 5, 7, 10, 12, 18 ja etsimme siihen numeroa 12.
Meillä on yhteensä 7 elementtiä, joten neljäs on keskiarvo, sen arvo on 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Koska 12 on suurempi kuin 7, voimme hylätä elementit 1,3 ja 5. Sitten meillä on 4 numeroa jäljellä, 4/2 ilman jäännöstä on 2. Joten uusi keskielementti on 10.
| 7 | 10 | 12 | 18 |
Keskimmäinen elementti on täällä jo 12, tämä on haluttu numero. Tehtävä valmis - numero 12 löytyi.
