Binárne vyhľadávanie - jeden z najjednoduchších spôsobov, ako nájsť prvok v matici

Docela často, programátori, a to aj pre začiatočníkov, tvárou v tvár s tým, že existuje niekoľko čísel, ktorá musí nájsť určitý počet. Je to práve táto kolekcia sa nazýva pole. A nájsť predmety v ňom, tam sú nespočetné množstvo spôsobov. Ale najjednoduchšie z nich možno považovať za binárne vyhľadávanie na pravej strane. Čo je to metóda? A ako vykonávať binárne vyhľadávanie? Pascal je najjednoduchšie prostredie pre organizovanie takéhoto programu, takže budeme používať k štúdiu.

Po prvé, analyzovať, aké sú výhody tohto postupu je tak môžeme pochopiť, aký je zmysel v štúdiu téme. Takže, poďme sa pole s rozmermi najmenej 100000000 prvky, ktoré je potrebné nájsť niektoré z nich. 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ém je v tom, že realizácia tejto myšlienky bude trvať príliš veľa času. 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. Zvlášť v prípade, že počítač je slabý výkon. Z tohto dôvodu je binárne vyhľadávanie, čo znižuje čas pri vyhľadávaní najmenej dvakrát.

Takže, čo je pracovný princíp tejto metódy? Ihneď treba povedať, že binárne hľadanie práce nie je v žiadnom poli, ale iba na triedený sadu čísel. V každom kroku prijatá stredného prvku matice (čo znamená, že množstvo prvku). V prípade, že požadovaný počet je vyšší, než je priemer, potom všetko, čo je vľavo, ktorá je menšia ako bežná bunka, môže byť zlikvidovaný, nesmie sa tam pozerať. A naopak, ak je menší ako je priemer - medzi týmito číslami na pravej strane, nemôžete vyhľadávať. Potom vyberte novú vyhľadávaciu priestor, kde bude prvý element byť strednej prvok celej poľa a posledný a poslednej vôle. Priemerný počet nového poľa bude ¼ všetkých segmentu, to znamená, že (posledný prvok + prostredný prvok celej pole) / 2. Opäť platí, že sa vykoná rovnaká operácia - porovnaní s priemerným počtom poľa. V prípade, že cieľová hodnota je nižšia ako priemer, odmietame na pravej strane, a tiež robiť ďalej, kým sa tento prostrednej element by nebolo žiaduce.

Samozrejme, že je najlepšie pozrieť sa na príklad, ako písať binárne vyhľadávanie. Pascal tu bude vyhovovať nikomu - verzia nie je dôležité. Poďme napísať jednoduchý program.

To je pole 1 až h pod názvom "masívu", premenná označujúca dolnú hranicu vyhľadávania, s názvom "NIZ", horná hranica, nazvaný "Verho", priemerná hľadaný výraz - "Srednji"; a požadovaný počet - "ISK".

Takže najprv musíme priradiť horná a dolná hranica hľadanie rozsah:

NIZ: = 1;
Verho: = h + 1;

Potom usporiadať cyklus "kým dolná časť je menšia ako horná hranica":

Kým NIZ začať

V každom kroku, delíme segment 2:

Srednji: = (NIZ + Verho) div 2; {Pomocou funkcie div, pretože delenie bez zvyšku}

Zakaždým, keď z preskúmania. Vzhľadom k tomu, položka už bolo konštatované, ak je to žiaduce médium, prerušenie cyklu:

іf Srednji = ISK potom zlomiť;

V prípade, že prostredný prvok poľa viac ako je žiaduce, vyradiť na ľavej strane, to znamená, že horná hranica priemeru menovať prvku:

ak MASSIVE [Sredni]> ISK potom Verho: = Srednji;

A ak je naopak, to je spodná hranica:

iný NIZ: = Srednji;
skončiť;

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

Uvažujme, ako to bude vyzerať binárne metódy v praxi. Zoberme si tento poľa: 1, 3, 5, 7, 10, 12, 18, a to sa bude snažiť číslo 12.

Celkom máme 7 prvky, takže bude štvrtá médium, hodnota 7.

Vzhľadom k tomu, viac ako 12, 7, 1,3 a 5 elementov, môžeme vyradiť. Potom máme číslo 4, 4/2 bezo zvyšku je 2. Takže nový prvok bude v priemere 10 rokov.

Vzhľadom k tomu, 12 je väčší ako 10, môžeme vyradiť 7. zostáva len 10, 12 a 18.

Tu je prostredný element je už 12, je požadované množstvo. Táto úloha je splnená - číslo 12 nájdený.