Binární vyhledávání-analýza algoritmu v jazyce c++

Ve vývoji programové vybavení pole se používají všude. "Inteligentní" datové typy v moderních programovací jazyk, například dynamická pole poskytují velké příležitosti pro pohodlnou práci s objekty. Algoritmy, které jsou základem práce s těmito typy dat, však byly vyvinuty v počátcích informatiky — v polovině dvacátého století. První binární vyhledávací algoritmus byl publikován v roce 1946.

Zvažte nejoblíbenější algoritmy pro provoz s poli.

Sekvenční (lineární) vyhledávání

Toto je nejjednodušší algoritmus pro nalezení hodnoty v poli. Používá metodu střídavého porovnávání prvků pole s hodnotou klíče. Provádí se obvykle zleva doprava. Používá se, pokud jsou prvky v poli trochu nebo seznam není uspořádán. Absolutně neefektivní ve velkých polích, kde se obvykle používá binární vyhledávání. Algoritmus funguje takto:

• Porovnáme hodnotu klíče s hodnota prvku masiv.
• Pokud jsou hodnoty stejné, vrátíme výslednou hodnotu.
• Pokud ne, zvýšíme hodnotu proměnné smyčky o jednu a porovnáme ji s dalším prvkem pole.

Indexové sekvenční vyhledávání

Efektivnější způsob hledání hodnoty v seřazeném poli. Ale náročnější na zdroje.

Binární vyhledávání

Binární (binární) vyhledávání je algoritmus pro nalezení prvku pole postupným rozdělením pole na polovinu a porovnáním původního čísla s číslem ze středu pole. Pokud je číslo ze středu menší než požadované číslo, hledáme další, ve druhé části, pokud je více, pokračujeme v hledání v první části. Algoritmus je nejrychlejší ze všech uvedených a funguje takto:

• Nejprve zjistíme hodnotu objektu uprostřed pole. Zkontrolujte shodu s původní hodnotou.
• Pokud je hodnota ze středu menší než původní, pokračujeme ve vyhledávání ve druhé polovině, pokud je více, hledáme v první.
• Ve výsledné polovině to děláme stejným způsobem: vydělíme to polovinou a porovnáme výslednou hodnotu.

K vyhledávání dochází až do okamžiku, kdy se původní hodnota nerovná hodnotě v poli. Pokud se to nestane, pak tato hodnota v poli není.

Při navrhování binárního vyhledávání se může setkat několik úskalí.

Přetečení vybraného datového typu

Chcete-li zjistit hodnotu uprostřed pole, musíte přidat pravou a levou hodnotu a rozdělit ji na dvě. To je:

Střed pole = levá hodnota + (levá hodnota je pravá hodnota) / 2

Při operaci sčítání existuje nebezpečí přetečení datového typu. Pokud má pole hodnoty tak velké velikosti, musíte použít různé triky, abyste se vyhnuli riziku. Níže jsou uvedeny standardní chyby při vývoji binárního vyhledávání.

Chyby hodnot

Nebo chyby na jednotku. Je velmi důležité zvážit následující možnosti:

• Prázdné pole.
• Význam chybí.
• Překročení hranice pole.

Více instancí

Je třeba vzít v úvahu, že v případě existence několika identických instancí klíče v poli musí program najít konkrétní (první, poslední, následující).

Pojďme analyzovat implementace tohoto algoritmu v programovacím jazyce C Plus Plus. Je třeba zvážit, že binární vyhledávání funguje pouze s seřazeným polem! Pokud pole není předem tříděno, bude výsledek výpočtu nesprávný.

Níže je kód v C ++. Nejprve je inicializováno pole celočíselných proměnných arr o velikosti deseti. Dále příkaz cin ve smyčce for čeká na zadání deseti hodnot od uživatele (řádek deset).

Ve dvacátém řádku program čeká na Zadání hodnoty klíče od uživatele.

Řádky 29 – 35 jsou implementovaným binárním vyhledávacím algoritmem. Během provádění programu se do proměnné mid zapíše hodnota průměrného prvku podle vzorce:

Střed pole (mid) = (levá hodnota ( l) + pravá hodnota (r))/2

Řádek

arr[mid]==key

Zkontroluje se, zda se střední hodnota rovná hodnotě klíče. Pokud se rovná, hodnota proměnné flag se změní na hodnotu true, tj.

Pokud je střední hodnota větší než hodnota našeho klíče, pak je pravé straně (proměnná r) přiřazeno mid. Pokud je to naopak, pak je mid vložen do r.

Poslední je kontrola booleovské proměnné flag.

Výhody binárního vyhledávání

Binární vyhledávání by mělo být použito, pokud potřebujete rychlý program. A psát takový algoritmus nebude obtížné ani pro začínajícího programátora. Je však velmi důležité vzít v úvahu všechny extrémní případy: překročení pole, chybějící hledaná hodnota, chyba přetečení dat.

Nedostatky

Aby algoritmus fungoval správně, musí být pole předem seřazeno. K tomu v programovacím jazyce C++ můžete použít hotovou funkci sort (). A další důležitý bod, který potřebujete všimnout si, učení binárního vyhledávání v C A C++. Tento algoritmus lze použít pouze s určitými datovými strukturami. Například struktury, které používají propojené seznamy, zde nebudou fungovat.