Kahendotsingupuu - üks lihtsamaid viise leida element massiivi

Üsna sageli, programmeerijad, isegi algajatele, silmitsi asjaoluga, et seal on arvude, mis peab leidma konkreetse numbriga. On see kogumine nimetatakse massiivi. Ja leida objekte see on hulgaliselt võimalusi. Aga kõige lihtsam neist võib pidada kahendotsingupuu paremal. Mis on see meetod on? Ja kuidas rakendada kahendotsingupuu? Pascal on lihtsaim keskkond organisatsiooni sellise programmi, nii et me kasutame seda uurida.

Esiteks analüüsida, millised on eelised seda meetodit, see on nii saame aru, Mis mõtet on uuringu teema. Niisiis, oletame, on massiivi mõõde vähemalt 100000000 elemente, mis on vaja leida mõned. Muidugi, seda probleemi saab kergesti lahendada lihtsa lineaarse otsingu, kus me kasutame tsükli võrrelda nõutava elemendi kõik need, mis on massiivi. Probleem on selles, et rakendamise idee võtab liiga palju aega. In lihtne Pascal programmi mitmeks ravi ja kolm rida põhiteksti, siis ei märka seda, kuid kui me enam-vähem suurte projektide suur hulk filiaale ja hea funktsionaalsus, programmi saab valmis koormatud liiga kaua. Eriti kui arvuti on nõrk jõudlust. Seetõttu on binaarne otsing, mis vähendab otsingut ajal vähemalt kaks korda.

Niisiis, milline on tööpõhimõte seda meetodit? Kohe tuleb öelda, et binaarne otsing töötab ei ole mingil massiiv, kuid ainult sorditud komplekt numbrid. Iga samm keskel massiivi element (st elemendi numbri). Kui vaja arv on suurem kui keskmine, siis kõik, mis on jäänud, mis on väiksem kui keskmine raku, võib visata ja seda ei vaadata seal. Vastupidisel juhul, kui vähem kui keskmine - nende seas numbrid paremale, siis ei saa otsida. Seejärel valige uut otsingut piirkond, kus esimene element on keset element kogu massiiv, ja viimane ja viimane tahe. Keskmine mitmeid uusi valdkonnas on ¼ kogu segment, mis on (viimane element + keset element kogu massiiv) / 2. Jällegi sama toimingut teostatud - võrdlus keskmine arv massiivi. Kui sihtväärtus on väiksem kui keskmine lükkame tagasi paremal pool, ja ka edasi teha, seni seda keset element ei soovitud.

Muidugi, see on kõige parem vaadata näide, kuidas kirjutada kahendotsingupuu. Pascal siin sobiks keegi - versioon ei ole oluline. Olgem kirjutada lihtne programm.

On hulgaliselt 1 h nime all "massiv", muutuja näitab alumise piiri otsingu, mida nimetatakse "niz", ülempiiri, mida nimetatakse "verh" keskmine otsingusõna - "sredn"; ja nõutava arvu - "Islandi".

Niisiis, esimene anname ülemine ja alumine piir vahemikus otsingut:

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

Siis korraldada tsükli "kuni põhi on vähem kui ülemine piir":

Kuigi niz alustama

Igal sammul, jagame segment 2:

sredn: = (niz + verh) div 2; {Kasutage funktsiooni div, sest lõhe ilma ülejäänud}

Iga kord läbi vaadata. Kuna toode on juba leitud, kui keskmise soovitakse katkestada tsükkel:

іf sredn = isk lõhutakse;

Kui keset element massiivi rohkem kui soovitud, visake vasakul pool, see on ülemine piir keskmisest nimetada element:

Kui Massiv [sredn]> isk siis verh: = sredn;

Ja kui vastupidi, see teeb alumise piiri:

teine niz: = sredn;
lõpetamiseks;

See on kõik, mis on programmis.

Mõelgem, kuidas ta otsib binaarne meetod praktikas. Mõelge sellele massiivi: 1, 3, 5, 7, 10, 12, 18 ja küsib ta number 12.

Kokku on meil 7 elementi, nõnda neljanda keskmise väärtus 7.

Kuna rohkem kui 12, 7, 1.3 ja 5 sätteid, saame visata. Siis on meil numbriga 4, 4/2 mingit jääki on 2. Niisiis, uus element on keskmiselt 10.

Kuna 12 on suurem kui 10, siis visake 7. jääb vaid 10, 12 ja 18.

Siin keset element on juba 12, siis on vajalik arv. See ülesanne on täidetud - number 12 leitud.