Tietokoneet, Ohjelmointi
Binäärihaku - yksi helpoimmista tavoista löytää elementti array
Usein ohjelmoijat, myös aloittelijat, sen tosiasian edessä, että on olemassa joukko numeroita, jotka on löydettävä tietty määrä. Juuri tämä kokoelma on nimeltään jono. Ja löytää kohteita on olemassa lukemattomia tapoja. Mutta yksinkertaisin niistä voidaan pitää binäärihaku oikealla. Mikä tämä menetelmä on? Ja miten toteuttaa binäärihakua? Pascal on helpoin ympäristö järjestämisestä tällaisen ohjelman, joten käytämme sitä opiskelemaan.
Ensinnäkin, analysoida, mitkä ovat tämän menetelmän eduista, se on niin voimme ymmärtää,
Joten, mikä on toimintaperiaate tämän menetelmän? Välittömästi sen pitäisi sanoa, että Binäärihaku toimii ei missään array, mutta vain lajitellun numerosarja. Kussakin vaiheessa otettu keskellä alkio (eli alkioiden lukumäärä). Mikäli vaadittu määrä on suurempi kuin keskimääräinen, niin jäljelle jää, joka on pienempi kuin keskimäärin solu, voidaan hävittää eikä näyttää siellä. Toisaalta, jos vähemmän kuin keskimäärin - joukossa numerot oikealle, et voi hakea. Valitse sitten uusi haku alue, jossa ensimmäinen elementti on keskellä osa koko ryhmän, ja viimeinen ja viimeinen tahto. Keskimääräinen uuden kentän on neljäsosa koko segmentin, joka on (viimeinen elementti + keskellä osa koko ryhmän) / 2. Uudelleen, sama toimenpide suoritetaan - vertailu keskimääräisestä jono. Jos kohde on pienempi kuin keskimäärin, hylkäämme oikealla puolella, ja myös tehdä seuraavaksi, kunnes nyt tämä keskielementtikoordinaatit ei haluttu.
Tietenkin se on parasta tarkastella esimerkki siitä, miten kirjoittaa binary haussa. Pascal täällä sopii kaikille - versio ei ole tärkeää. Kirjoitetaan yksinkertainen ohjelma.
Se on joukko 1 h nimellä "massiv", muuttuja, joka ilmaisee alaraja haku, nimeltään "niz", yläraja, jota kutsutaan "Verh" keskimääräinen hakusana - "sredn"; ja tarvittava määrä - "ISK".
Joten, ensin asetamme ylä- ja alaraja aikavälihaussa:
niz: = 1;
Verh: = h + 1;
Sitten järjestää sykli "kunnes pohja on pienempi kuin yläraja":
Vaikka niz
Kussakin vaiheessa, me jakaa segmentti 2:
sredn: = (niz + Verh) div 2; {Käytä toiminto div, koska kuilun ilman loput}
Joka kerta laillisuuden. Koska tuote on jo todettu, jos väliaine halutaan, keskeyttää sykli:
іf sredn = ISK sitten tauko;
Jos keskellä alkio enemmän kuin haluttu, hävitä vasemmalla puolella, eli ylärajan keskimääräinen nimittää elementti:
jos Massiv [sredn]> ISK sitten Verh: = sredn;
Ja jos päinvastoin, se tekee alaraja:
else niz: = sredn;
end;
Siinä kaikki, jotka ovat ohjelmassa.
Mietitäänpä, miten se näyttää binary menetelmää käytännössä. Harkita tämän taulukon: 1, 3, 5, 7, 10, 12, 18 ja se pyrkii numero 12.
Yhteensä meillä on 7 elementtejä, niin tulee neljäs väliaine, arvo 7.
1 | 3 | 5 | 7 | 10 | 12 | 18 |
Koska yli 12, 7, 1,3 ja 5 elementit, voimme hävitä. Sitten meillä numero 4, 4/2 ei ole jäämiä on 2. Niin, uusi elementti on keskimäärin 10.
7 | 10 | 12 | 18 |
Täällä, keskimmäinen elementti on jo 12, on tarvittava määrä. Tämä tehtävä on suoritettu - numero 12 löydetty.
Similar articles
Trending Now