Dvejetainiai paieška - vienas iš paprasčiausių būdų, kaip rasti masyve elementą

Gana dažnai, programuotojai, net pradedantiesiems, susiduria su tuo, kad yra skaičių rinkinys, kuris turi rasti tam tikrą skaičių. Būtent ši kolekcija yra vadinamas masyvo. Ir rasti elementus jį, yra daug būdų, kaip daugybė. Bet pats paprasčiausias iš jų gali būti laikomas dvejetainis paieškos dešinėje. Kas yra šis metodas yra? Ir kaip įgyvendinti dvejetainis paiešką? Pascal yra lengviausias aplinka už tokią programą organizacijoje, todėl mes naudosime ją studijuoti.

Pirma, analizuoti, kas yra šio metodo privalumai, tai yra, kad mes galėtume suprasti, kas yra į temą studijų vieta. Taigi, galime daryti su bent 100000000 elementų, kuriuos reikia rasti kai dimensijos masyvo. Žinoma, ši problema gali būti lengvai išspręsta paprastu linijiniu paieškoje, kurioje mes naudojame ciklą bus palyginti reikiamą elementą su visais tais, kurie yra masyve. Problema yra ta, kad šios idėjos įgyvendinimas užtruks daug laiko. Paprastu Pascal programa į keletą gydymo ir trijų eilučių pagrindinio teksto, jūs nepastebėsite, bet kai mes einame į daugiau ar mažiau didelių projektų su daug šakų ir gero funkcionalumo, programa bus pasirengusi būti pakrautas per ilgai. Ypač, jei kompiuteris yra silpnas veikimas. Todėl yra dvejetainė paieška, kuri sumažina paieškos laiką bent du kartus.

Taigi, kas yra darbo principas šiuo metodu? Iškart reikia pasakyti, kad dvejetainis paieškos veikia jokiu masyvo, bet tik ant rūšiavimo skaičių rinkinio. Kiekvienu žingsnis viduriniosios elemento masyvo (tai reiškia, elemento numerį). Jei reikia , skaičius yra didesnis nei vidutiniškai, tada viskas, kas liko, tai yra mažiau nei vidutinis ląstelių, gali būti atmesta, o ne ten atrodo. Ir atvirkščiai, jei mažiau nei vidutiniškai - tarp tų skaičių į dešinę, jūs negalite paiešką. Tada pasirinkite naują paieškos zoną, kur pirmasis elementas bus vidutinio elementas visą masyvą, o paskutinis ir paskutinis noras. Vidutinis skaičius naują srityje bus ¼ visų segmento, tai yra, (paskutinio elemento + vidurinės elemento visą masyvas) / 2. Vėlgi, pati operacija atliekama - palyginti su vidutiniu skaičiumi masyvo. Jei tikslinė vertė yra mažesnė nei vidurkis, mes atmetame dešinėje pusėje, o taip pat daryti toliau, iki šiol tai vidutinio elementas nebūtų pageidaujama.

Žinoma, tai geriausia pažvelgti, kaip rašyti dvejetainis paiešką pavyzdyje. Pascal čia tiks visiems - versija nėra svarbi. Leiskite parašyti paprastą programą.

Tai iš 1 masyvas h pagal pavadinimą "MASSIV", kintamasis, nurodantis apatinę ribą paieškos, vadinama "niz", viršutinė riba, vadinama "Verh", vidutinė paieškos terminas - "sredn"; ir reikiamą skaičių - "ISK".

Taigi, pirmiausia mes priskirti viršutinę ir apatinę ribą nuotolio paieškos:

niz: = 1;
Verh: = h + 1;

Tada organizuoja ciklą "iki apačios yra mažesnis nei viršutinės ribos":

Nors niz pradėti

Kiekviename žingsnyje, mes padalinti segmentą 2:

sredn: = (niz + Verh) div 2; {Naudoti funkcijos div, nes atskirties be likusiam}

Kiekvienas peržiūros metu. Kadangi daiktas jau rasti, jei vidutinės norima, nutraukti ciklą:

jei sredn = izikos tada pertrauka;

Jei vidutinio elementas masyve daugiau nei reikia, išmesti iš kairės pusės, tai yra, viršutinė riba vidutiniškai skiria elementas:

jei MASSIV [sredn]> izikos tada Verh: = sredn;

O jei priešingai, tai daro apatinės ribos:

kitur niz: = sredn;
galų;

Tai viskas, kad bus programoje.

Panagrinėkime, kaip jis atrodys dvejetainis metodą praktikoje. Apsvarstykite šį masyvas: 1, 3, 5, 7, 10, 12, 18 ir ji sieks skaičių 12.

Iš viso turime 7 elementus, todėl bus ketvirtas vidutinio, vertė 7.

Nes daugiau nei 12, 7, 1.3 ir 5 elementų, galime išmesti. Tada mes turime numeris 4, 4/2 jokių likučių yra 2. Taigi, naujas elementas bus 10 vidurkis.

Nuo 12 yra didesnis nei 10, mes išmesti 7. lieka tik 10, 12 ir 18.

Čia, viduryje elementas yra jau 12, tai yra reikiamas skaičius. Ši užduotis yra baigtas - skaičių 12 rasta.