Ve vývoji softwaru se pole používají všude. Inteligentní datové typy v moderních programovacích jazycích, jako jsou dynamické pole, poskytují velké možnosti pro pohodlnou práci s objekty. Ale algoritmy založené na práci s těmito typy dat, které byly vyvinuty na úsvitu počítačové vědy - v polovině dvacátého století. První algoritmus pro binární vyhledávání byl publikován v roce 1946. Zvažte nejoblíbenější algoritmy pro manipulaci s maticemi.
Sekvenční vyhledávání
Jedná se o nejjednodušší algoritmus pro nalezení hodnoty v poli. Používá metodu střídání porovnání prvků pole s hodnotou klíče. Obvykle se provádí zleva doprava. Používá se, pokud položky v poli jsou mírně mimo seznam. Absolutně neúčinné v rozsáhlých polích, kde se obvykle používají binární vyhledávání. Algoritmus funguje takto:
Porovnejte hodnotu klíče s hodnotou prvku pole.
Pokud jsou hodnoty stejné, vrátíme výslednou hodnotu.
Pokud ne, zvýšíme hodnotu proměnné cyklu o jednu a srovnáme s dalším prvkem pole.
Indexové sekvenční vyhledávání
Účinnější způsob, jak najít hodnoty v tříděné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 dělením pole na polovinu a porovnáním výstupu s číslem ze středu pole.Pokud je číslo od středu menší než požadované, budeme hledat dále, v druhé části, pokud je více - pokračujeme v hledání v prvním. Algoritmus je nejrychlejší ze všech uvedených a pracuje takto:
Nejprve zjistíme hodnotu objektu uprostřed pole. Zkontrolujte, zda odpovídá původní hodnotě.
Pokud je hodnota od středu menší než původní, pokračujeme ve vyhledávání v druhé polovině, pokud je více - hledáme první.
Ve výsledné polovině postupujte stejným způsobem: rozdělte jej na polovinu a porovnejte získanou hodnotu.
Hledání probíhá, dokud se původní hodnota nestane rovna hodnotě v poli. Pokud se tak nestane - tato hodnota v poli neexistuje.
Existuje několik úskalí, se kterými se můžete setkat při navrhování binárního vyhledávání.
Přetečení vybraného datového typu
Chcete-li najít hodnotu ve středu pole, je třeba provést pravou a levou hodnotu a rozdělit dvěma. To znamená:Uprostřed pole = Levá hodnota + (Levá hodnota - Pravá hodnota) /2
Při operaci přidávání existuje nebezpečí přetečení datového typu. Pokud je pole tak veliké, musíte se vyhnout riziku pomocí různých technik. Níže jsou standardní chyby při navrhování binárních vyhledávání.
Chyby hodnot
Nebo chyby na jednotku. Je velmi důležité zvážit následující možnosti:
Prázdné pole.
Žádná hodnota.
Překročení pole.
Vícenásobné kopie
Je třeba poznamenat, žePokud existuje řada shodných kopií programu prací musí najít a (první, poslední, po tom).
Pokud potřebujete rychlou programovou operaci, použijte binární vyhledávání. A psát takový algoritmus neublíží ani začínajícímu programátorovi. Je však velmi důležité vzít v úvahu všechny extrémní případy: mimo hranice pole, absence požadované hodnoty, chyba přetečení dat.
Nevýhody
Pro správnou funkci algoritmu musí být pole předřazené. Chcete-li to provést, můžete použít funkci řazení sort () v programovacím jazyce C ++. A ještě jeden důležitý bod, který byste měli hledat při studiu binárního vyhledávání v jazycích 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 nejsou vhodné.
