7. Binar izlew (teń ekige bόliw usılı)
Meyli, όsiw tártibinde tártiplengen sanlar massiv berilgen bolsın. Usı usıldı tiykarǵı ideası sonnan ibarat, tosınnan qandayda bir AM element alınadı hám ol X izlew argumenti menen salıstırıladı. Eger AM=Xbolsa, ol jaǵdayda tamamlanadı; eger AM bolǵan barlıq elementlerdi kelesi izlewdan shıǵarıp jiberiledi. Tap usınday,eger AM >X bolsa.
M qálegen túrde saylanǵanda da usınılıp atırǵan algoritm korrekt isleydi. Sol sebepli M di sonday etip saylap alıw kerek, izertlenip atırǵan algoritm effektiv nátiyje bersin, yaǵniy onı sonday etip saylap alayıq, ilaji barınsha kelesi processte qatnasıwshı elementler sanı kem bolsın.Eger bizler ortasha elementti, yaǵniy massiv ortasın tańlasaq sheshim quramalı boladı.
Tόmendegi sızılma kόrinisinde berilgen massivti qarastırıp όteyik. Meyli, bizden giltti 52 ge teń bolǵan elementti tabıw talap etilsin. Dáslepki salıstırılatuǵin
element 49 boladı. 49<52 bolǵanı ushın sebebi, 49 dan joqarıda turǵan elementler ortasında ámelge asırıladı. Jańa payda bolǵan massiv ortası 86. Eger berilgen gilt penen usı giltti salıstırsaq 86>52 boladı. Demek, náwbettegi izlewler 86 menen 49 ortasındaǵi ishinde ámelge asırılıwı lazım. Keyingi adımda belgili boladı, qaralıp atırǵan elementler ortasındaǵi element giltti 52 ge teń. Sonday qılıp, massivde berilgen giltge teń bolǵan elementti taptıq.
Joqarıdaǵı algoritmdi ámelge asırıw programması C++ tilinde tόmendegishe
boladı:
Eger key = 101 bolsa, kerekli jazıw 3 márte salıstırıwlarda anıqlanadı ( izbe-iz
izlewda salıstırıwlar sanı 7 ta bolar edi).
Eger S –salıstırıwlar sanı hám n – kestedegi elementler sanı bolsa, ol jaǵdayda
S = log2n.
Máselen, n = 1024.
Ízbe-iz izlewda S = 512, binar izlewda S = 10.
Eger úlken kόlemdegi maǵluwmatlar ishinde izlew ámelge asırılıp atırǵan bolsa, ol jaǵdayda binar hám indeksli izbe-iz izlewdı ulıwmalastırıp alıp barıw múmkin. Sebebi, hár eki izlewda tártiblengen massivde ámelge asırıladı.
52>
Do'stlaringiz bilan baham: |