Binary bilaketa array batean elementu bat aurkitzeko modurik errazena da

Sarritan, programatzaileek nahiz hasiberriek zenbaki jakin bat behar dute zenbaki multzo bat aurkitzeko. Bilduma honek array bat deitzen da. Eta elementu eskubidea aurkitzeko, modu asko daude. Baina horien artean errazena bilaketa bitarra da. Zein da metodoa? Eta bilaketa bitar bat nola ezarri? Pascal-ek programa hori antolatzeko ingurune errazena da, beraz azterketa egiteko erabiliko dugu.

Lehenik, metodo honen abantailak aztertuko ditugu, azken finean, ulertu ahal izateko, Zer da gaia aztertzea? Beraz, uste al duzu array bat gutxienez 10.000.000.000 elementuren dimentsio bat dela? Bertan, jakin bat aurkitu behar duzu. Jakina, arazoa erraz daiteke bilaketa lineal sinple baten bitartez konpondu ahal izateko, eta bertan begizta bat erabiltzen dugu arrayan dauden elementu guztiak nahi duzun elementua alderatzeko. Arazoa da ideia hori ez dela gehiegi hartuko. Prozedura askoko Pascal programu bakarrean eta testu nagusiaren hiru lerroekin, ez duzu nabarituko, baina proiektu handiago edo gutxiago abiarazten eta funtzionalitate onarekin asko hasten zarenean, amaitutako programa luzeegia izango da. Batez ere, ordenagailuak errendimendu eskasa badu. Hori dela eta, bilaketa binario bat dago, gutxienez birritan bilaketa denbora murrizten duena.

Beraz, zein da metodo honen printzipioa? Berehala merezi du bilaketa bitarrak ez duela arrayetan funtzionatzen, baizik eta zenbaki multzo ordenatuetan bakarrik. Hurrengo pauso bakoitzean, arrayaren batez besteko elementua hartzen da (elementuen zenbakiari erreferentzia egiten dio). Nahi duzun zenbakia batez bestekoa baino handiagoa bada, ezkerreko dena, hau da, batez besteko elementua baino txikiagoa, baztertu eta ez da bilatu. Alderantziz, batez bestekoa baino gutxiago, eskuineko zenbakien artean, ezin dituzu bilatu. Ondoren, bilaketa-eremu berri bat hautatuko dugu, non lehenengo elementua array osoaren erdiko elementua izango den eta azkenekoa azkenekoa izango da. Area berriaren batez besteko kopurua ¼ segmentu osoa izango da, hau da (azken elementua + array osoaren batez besteko elementua) / 2. Berriz ere, eragiketa bera egiten da: arrayaren batez besteko zenbakiarekiko konparazioa. Nahi duzun balioa batez bestekoa baino txikiagoa bada, eskuinera baztertu eta gauzatu erdiko elementu hau arte.

Jakina, adibide bat bilatzeko modurik onena bilaketa bitarra idaztea da. Pascal hemen edonorentzat egokia da - bertsioa ez da garrantzitsua. Programa sinple bat idaztea.

"1" izeneko array bat izango du, "masib" izenekoa, beheko bilaketa-muga adierazten duen aldagai bat, "niz" deitzen den aldagai bat, "verh" izeneko goi-barrutia, erdiko bilaketa elementua "sredn" da; Beharrezko zenbakia "isk" da.

Beraz, bilaketa-tartearen goiko eta beheko mugak esleitu:

Niz: = 1;
Verh: = h + 1;

Ondoren zikloa antolatu dugu "beheko goiko muga baino txikiagoa den bitartean":

Niz hasiko

Urrats bakoitzean, zatitzea segmentua 2:

Sredn: = (niz + verh) div 2; {Erabili div funtzioa gainerakoa zatitzen dugulako}

Aldi bakoitzean txeke bat egiten dugu. Batez bestekoa nahi denaren berdina bada, zikloa eten egingo dugu, nahi den elementua dagoeneko aurkitu delako:

Sredn = isk gero hautsi;

Arrayaren erdiko elementua bilatzen ari garen baino handiagoa baldin badugu ezkerrera baztertzen dugu, hau da, erdiko elementua goiko muga esleitzen dugu:

Massiv [sredn]> isk bada, orduan: = sredn;

Eta alderantziz gero, beheko muga egiten dugu:

Else niz: = sredn;
bukatzen;

Hori guztia izango da programa.

Metodo binarioak praktikan nola aztertuko duen aztertuko dugu. Hartu array bat: 1, 3, 5, 7, 10, 12, 18 eta bilatu 12 zenbakia.

Guztira, 7 elementu ditugu, beraz, batez bestekoa laugarrena izango da, bere balioa 7koa.

12tik 12 baino handiagoa denez, 1,3 eta 5 elementuak baztertu egin daitezke. Hurrengoa, 4 zenbaki falta ditugu, 4/2 eta gainerakoak ez dira 2. Beraz, erdiko elementu berria 10 izango da.

12 urtetik gorako 10 baino gehiago, 7 baztertuko ditugu. 10, 12 eta 18 bakarrik geratzen dira.

Hemen erdiko elementua 12 da dagoeneko, hau da beharrezkoa den zenbakia. Ataza amaituta dago, 12 zenbakia aurkitu da.