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

Polia sa používajú všade pri vývoji softvéru. . "Inteligentné" dátové typy v modernom programovacie jazyky, , ako napríklad dynamické polia, poskytujú veľké príležitosti pre pohodlnú prácu s objektmi. Ale algoritmy, ktoré sú základom práce s týmito typmi údajov, boli vyvinuté na úsvite počítačovej vedy — v polovici dvadsiateho storočia. Prvý algoritmus binárneho vyhľadávania bol publikovaný v roku 1946.

, Pozrime sa na najobľúbenejšie algoritmy pre prácu s poľami.

Sekvenčné (lineárne) vyhľadávanie

Toto je najjednoduchší algoritmus na nájdenie hodnoty v poli. Používa metódu striedavého porovnávania prvkov poľa s hodnotou kľúča. Vykonáva sa normálne, zľava doprava. Používa sa, ak je v poli málo prvkov alebo zoznam nie je objednaný. Je to absolútne neúčinné vo veľkých poliach, kde sa zvyčajne používa binárne vyhľadávanie. Algoritmus funguje nasledovne:

• Porovnajte hodnotu kľúča s hodnota z prvku poľa.
• Ak sú hodnoty rovnaké, vrátime prijatú hodnotu.
• Ak nie, zvýšime hodnotu premennej slučky o jednu a porovnáme ju s ďalším prvkom poľa.

Index-sekvenčné vyhľadávanie

Efektívnejší spôsob, ako nájsť hodnotu v zoradenom poli. Ale náročnejšie na zdroje.

Binárne vyhľadávanie

Binárne (binárne) vyhľadávanie je algoritmus na nájdenie prvku poľa postupným rozdelením poľa na polovicu a porovnaním pôvodného čísla s číslom zo stredu poľa. Ak je číslo od stredu menšie ako číslo, ktoré hľadáte, hľadáme ďalej v druhej časti, ak je viac, pokračujeme v hľadaní v prvej. Algoritmus je najrýchlejší zo všetkých uvedených a funguje nasledovne:

• Najprv zistíme hodnotu objektu v strede poľa. Skontrolujte súlad s pôvodnou hodnotou.
• Ak je hodnota od stredu menšia ako pôvodná, potom pokračujeme v hľadaní v druhej polovici, ak je viac, hľadáme v prvej.
• Vo výslednej polovici robíme to isté: rozdelíme ju na polovicu a porovnáme výslednú hodnotu.

Vyhľadávanie sa uskutoční, kým sa počiatočná hodnota nerovná hodnote v poli. Ak sa tak nestane, táto hodnota nie je v poli.

Pri navrhovaní binárneho vyhľadávania sa môže vyskytnúť niekoľko nástrah.

Pretečenie vybraného typu údajov

Ak chcete zistiť hodnotu v strede poľa, musíte spočítať pravú a ľavú hodnotu a vydeliť dvoma. To je:

Stred poľa = Ľavá hodnota + (ľavá hodnota-pravá hodnota)/2

Počas operácie pridávania existuje nebezpečenstvo pretečenia dátového typu. Ak sú v poli hodnoty takých veľkých veľkostí, musíte použiť rôzne techniky, aby ste sa vyhli riziku. Nižšie sú uvedené štandardné chyby vo vývoji binárneho vyhľadávania.

Chyby hodnoty

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

• Prázdne pole.
• Hodnota chýba.
• Prekročenie hraníc poľa.

Viaceré inštancie

Malo by sa vziať do úvahy, že ak existuje niekoľko identických inštancií kľúča v poli, program musí nájsť určité (prvé, posledné, vedľa neho).

Poďme analyzovať implementáciu tohto algoritmu v programovacom jazyku C plus plus. Majte na pamäti, že binárne vyhľadávanie funguje iba s zoradeným poľom! Ak Pole nie je vopred zoradené, výsledok výpočtov bude nesprávny.

Nižšie je uvedený kód v C ++. Najprv sa inicializuje pole celočíselných premenných arr, veľkosť desať. Ďalej operátor cin v slučke for čaká na zadanie desiatich hodnôt od používateľa (riadok desať).

V dvadsiatom riadku program čaká, kým používateľ zadá hodnotu kľúča.

Riadky 29 – 35 predstavujú implementovaný binárny vyhľadávací algoritmus. Počas vykonávania programu sa hodnota stredného prvku zapíše do strednej premennej podľa vzorca:

Stred poľa (mid) = (ľavá hodnota (l) + pravá hodnota (r)) / 2

Podľa reťazca

arr [mid]==kľúč

Skontroluje, či sa stredná hodnota rovná kľúčovej hodnote. Ak je rovnaká, potom sa hodnota premennej príznaku zmení na hodnotu TRUE, to znamená, že problém je vyriešený.

Ak je stredná hodnota väčšia ako hodnota nášho kľúča, potom je pravá časť (premenná r) priradená mid. Ak naopak, potom sa do r vloží mid.

Posledným z nich je kontrola logického príznaku premennej.

Výhody binárneho vyhľadávania

Binárne vyhľadávanie by sa malo použiť, ak program potrebuje rýchlu prevádzku. A nebude ťažké napísať takýto algoritmus ani pre začínajúceho programátora. Je však veľmi dôležité vziať do úvahy všetky extrémne prípady: opustenie poľa, chýbajúca požadovaná hodnota, chyba pretečenia údajov.

Nevýhoda

Aby algoritmus fungoval správne, musí byť pole vopred zoradené. Na tento účel môžete v programovacom jazyku C++ použiť hotovú funkciu sort() . A ďalší dôležitý bod, ktorý potrebujete venovať pozornosť, pri štúdiu binárneho vyhľadávania v C A C++. Tento algoritmus je možné použiť iba s určitými dátovými štruktúrami. Napríklad tu nebudú fungovať štruktúry používajúce prepojené zoznamy.