Binárne vyhľadávanie - analýza algoritmu v jazyku C ++

Vo vývoji softvéru sú pole používané všade. Inteligentné dátové typy v moderných programovacích jazykoch, ako napríklad dynamické súbory, poskytujú skvelé možnosti pre pohodlnú prácu s objektmi. Ale algoritmy, ktoré sú základom práce s týmito typmi dát, ktoré boli vyvinuté na začiatku počítačovej vedy - v polovici dvadsiateho storočia. Prvý algoritmus pre binárne vyhľadávanie bol zverejnený v roku 1946. Zvážte najobľúbenejšie algoritmy pre manipuláciu s políčkami.

Sekvenčné vyhľadávanie

Toto je najjednoduchší algoritmus na vyhľadanie hodnoty v poli. Používa metódu alternatívneho porovnávania prvkov poľa s kľúčovou hodnotou. Obvykle sa vykonáva zľava doprava. Používa sa, ak sú položky v poli mierne mimo zoznamu. Absolútne neefektívne v rozsiahlych poliach, kde sa bežne používajú binárne vyhľadávania. Algoritmus funguje nasledovne:


  • Porovnajte hodnotu kľúča s hodnotou prvku poľa.
  • Ak sú hodnoty rovnaké, výslednú hodnotu vrátime.
  • Ak nie, zvýšime hodnotu premennej cyklu o jednu a porovnáme s ďalším prvkom poľa.
  • Indexovo-sekvenčné vyhľadávanie

    Účinnejší spôsob, ako nájsť hodnoty v triedenom poli. Ale náročnejšie na zdroje.

    binárne vyhľadávanie

    Binárne (binárne) vyhľadávanie - algoritmus z postupného prvok poľa rozdeľujúce polovicu poľa a sravnyvanyem originálne číslo číslom od stredu poľa.Ak je číslo od stredu nižšie ako požadované, pozeráme ďalej, v druhej časti, ak je viac - pokračujeme v hľadaní v prvom. Algoritmus je najrýchlejší zo všetkých uvedených a funguje takto:


  • Najprv zistíme hodnotu objektu v strede poľa. Skontrolujte, či zodpovedá pôvodnej hodnote.
  • Ak je hodnota zo stredu menšia ako hodnota originálu, pokračujeme v hľadaní v druhej polovici, ak je viac - hľadáme prvú.
  • Vo výslednej polovici postupujte rovnakým spôsobom: rozdeľte ho na polovicu a porovnajte získanú hodnotu.
  • Vyhľadávanie prebieha, kým sa počiatočná hodnota nestane rovnou hodnote v poli. Ak sa tak nestane - táto hodnota v poli neexistuje.
    Existuje niekoľko nástrah, ktoré sa môžu vyskytnúť pri navrhovaní binárneho vyhľadávania.

    Pretečenie vybraného typu údajov

    Ak chcete nájsť hodnotu v strede poľa, musíte urobiť pravú a ľavú hodnotu a rozdeliť dve. To znamená:Stred pole = ľavá hodnota + (ľavá hodnota - pravá hodnota) /2

    Počas operácie pridania existuje nebezpečenstvo pretečenia dátového typu. Ak je pole tak veľké, musíte sa vyhnúť riziku pomocou rôznych techník. Nižšie sú uvedené štandardné chyby pri navrhovaní binárnych vyhľadávaní.

    Chyby hodnôt

    Alebo chyby na jednotku. Je veľmi dôležité zvážiť tieto možnosti:

    • Prázdne pole.
    • Žiadna hodnota.
    • Prekročenie poľa.

    Viaceré kópie

    Treba poznamenať, žeV prípade existencie niekoľkých identických príkladov kľúča v poli musí program nájsť určitý (prvý, posledný, nasledujúci).


    Binárne vyhľadávanie by sa malo použiť, ak potrebujete rýchlu operáciu. A napísať takýto algoritmus neublíži ani začínajúcemu programátorovi. Je však veľmi dôležité zohľadniť všetky extrémne prípady: mimo hranice poľa, neprítomnosť požadovanej hodnoty, chyba pretečenia dát.

    Nevýhody

    Pre správnu funkciu algoritmu musí byť pole predtriedené. Ak chcete urobiť, môžete použiť hotovú funkciu sort () v programovacom jazyku C ++. A ešte jeden dôležitý bod, ktorý treba hľadať pri štúdiu binárneho vyhľadávania v C a C ++. Tento algoritmus možno použiť iba s určitými dátovými štruktúrami. Napríklad štruktúry, ktoré používajú prepojené zoznamy, nie sú vhodné.

    Súvisiace publikácie