Binárne vyhľadávanie je jedným z najjednoduchších spôsobov, ako nájsť prvok v poli

Docela často, programátori, dokonca aj začiatočníci,že existuje množina čísel, v ktorých je potrebné nájsť určité číslo. Táto kolekcia sa nazýva pole. A nájsť v ňom správny prvok, existuje veľa spôsobov. Ale najjednoduchšie medzi nimi právo môže byť považované za binárne vyhľadávanie. Aká je metóda? A ako implementovať binárne vyhľadávanie? Pascal je najjednoduchším prostriedkom na organizáciu takéhoto programu, takže ho budeme používať na štúdium.

Po prvé, budeme analyzovať, aké výhody tejto metódy sú napokon, aby sme mohli pochopiť,

aký je zmysel študovať túto tému. Predpokladajme, že existuje pole s rozmermi najmenej 100000000 prvkov, v ktorých musíte nájsť určitý. Samozrejme, že tento problém sa dá ľahko vyriešiť jednoduchou lineárne vyhľadávanie, v ktorom sme pomocou cyklu porovná požadovaný prvok s tými, ktoré sú v poli. Problémom je, že implementácia tejto myšlienky bude trvať príliš dlho. V jednoduchom Pascal programe do niekoľkých procedúr a tri riadky hlavného textu, budete nevšimol, ale keď sme prišli na viac či menej rozsiahlych projektov s veľkým počtom pobočiek a dobrú funkčnosť, bude program pripravený na načítanie príliš dlho. Najmä v prípade, že počítač má slabý výkon. Preto existuje binárne vyhľadávanie, ktoré skracuje čas vyhľadávania najmenej dvakrát.

Takže, čo je to princíp prácemetóda? Stojí za zmienku, že binárne vyhľadávanie nefunguje v žiadnom poli, ale iba v triedenom počte čísel. Pri každom ďalšom kroku sa vykoná stredný prvok poľa (s odkazom na číslo prvku). Ak je požadované číslo väčšie ako priemer, potom všetko, čo je vľavo, to znamená menej ako priemerný prvok, sa môže zlikvidovať a tam sa nemôže vyhľadávať. Naopak, ak je menej ako priemer, medzi číslami vpravo ich nemôžete hľadať. Potom vyberieme novú oblasť vyhľadávania, kde stredný prvok celého poľa bude prvým prvkom a ten posledný zostane posledným. Priemerný počet novej oblasti bude ¼ celého segmentu, tj (posledný prvok + priemerný prvok celého poľa) / 2. Opäť sa vykoná rovnaká operácia - porovnanie s priemerným počtom polí. Ak je požadovaná hodnota nižšia ako priemer, odstráňte pravú stranu a urobte to isté, až kým sa nenájde tento stredný prvok.

Samozrejme, je najlepšie pozrieť sa na príklad toho, ako je napísané binárne vyhľadávanie. Pascal tu je vhodný pre každého - verzia nie je dôležitá. Napíšeme jednoduchý program.

Bude mať pole od 1 do h názvom"massiv", premenná označujúca nižšiu hranicu vyhľadávania nazvanú "niz", horná hranica s názvom "verh", stredný prvok vyhľadávania je "sredn"; a požadované číslo je "isk".

Takže najprv priraďte horné a dolné hranice vyhľadávacieho intervalu:

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

Potom zorganizujeme cyklus "zatiaľ čo nižšia je nižšia ako horná hranica":

Kým niz <verh - 1 robiť
začať

V každom kroku segment rozdeľte o 2:

sredn: = (niz + verh) div 2; {použite funkciu div, pretože zdieľame bez vyváženia}

Zakaždým, keď kontrolujeme. Ak sa priemer rovná požadovanému priemeru, prerušíme tento cyklus, pretože už bol nájdený potrebný prvok:

ak sredn = isk potom break;

Ak je stredný prvok poľa väčší než požadovaný, zlikvidujte ľavú stranu, to znamená, že stredný prvok je nastavený ako horná hranica:

ak massiv [sredn]> isk potom verh: = sredn;

A ak naopak, urobíme to nižšiu hranicu:

iný niz: = sredn;
skončiť;

To je všetko, čo bude v programe.

Pozrite sa, ako binárna metóda bude vyzerať v praxi. Vezmime nasledujúce pole: 1, 3, 5, 7, 10, 12, 18 a budeme hľadať číslo 12 v ňom.

Celkovo máme sedem prvkov, takže priemer bude štvrtý, jeho hodnota je 7.

Keďže 12 je väčšie ako 7, môžeme odložiť prvky 1.3 a 5. Potom máme 4 čísla vľavo, 4/2 bez vyváženia je 2. To znamená, že nový stredný prvok bude 10.

Keďže 12 je väčší ako 10, klesáme 7. Len 10, 12 a 18 zostávajú.

Tu je stredný prvok už 12, toto je požadované číslo. Úloha bola dokončená - bolo nájdené číslo 12.