Při vývoji algoritmů pro řešení mnoha problémů často nastává problém s implementací hledání určité skupiny dat podle zadaných kritérií. Při prozkoumávání uspořádané nebo neuspořádané sekvence lze vyhledávání provádět pomocí různých metod. Obecně platí, že k vyřešení problému s hledáním je uvažováno určité datové pole, ve kterém je nutné najít daný prvek.
Instrukce
Krok 1
Nejjednodušší způsob, jak najít známý prvek v datovém poli, je iterace nad jeho hodnotami. Tento algoritmus je optimální pro malé množství informací. Jeho podstata spočívá v procházení známé datové sekvence (pole) a porovnání každého prvku s požadovanou hodnotou. Pokud je nalezena shoda, v závislosti na zadaných kritériích lze hledání dokončit nebo pokračovat až do konce pole.
Krok 2
I přes jednoduchost implementace této metody je však její použití v polích obsahujících velké množství informací nežádoucí, protože to významně zvyšuje intenzitu zdroje algoritmu. Chcete-li v tomto případě optimalizovat hledání, je lepší předem třídit hodnoty v poli a implementovat vyhledávací algoritmy: binárním stromem, stromem Fibonacci, metodou extrapolace.
Krok 3
Při práci s uspořádaným polem použijte účinnější algoritmus - metodu binárního vyhledávání. Jeho podstata spočívá ve skutečnosti, že v procesu výčtu hranic intervalu se blíží k sobě, čímž se zužuje oblast hledání. Porovnejte hledanou hodnotu s očíslovaným prvkem pole. Pokud se vzorek shoduje s prvkem, považuje se problém za vyřešený. Pokud je požadovaná položka větší než prostřední prvek, pak je třeba provést další vyhledávání v části pole umístěné napravo od středního prvku (od začátku pole do středního prvku-1). Pokud je hledání menší než prostřední prvek, pak hledání pokračuje v části pole od středního po poslední prvek. Po určení nové oblasti pro vyhledávání se popsaný algoritmus opakuje, identifikuje shody nebo zužuje oblast zpracování. Toto schéma je správné pro sestupné pole.
Krok 4
Zvláštní problémy s nalezením minimálního nebo maximálního prvku v dané posloupnosti jsou vyřešeny přiřazením počátečního prvku jako požadovaného. Dále se provádí sekvenční výčet zbývajících hodnot pole: druhá s první, třetí s první atd. Při porovnávání hodnoty považované za standard je zřejmé, zda je v poli prvek, který je konzistentnější s danou podmínkou (minimální nebo maximální). Když je jeden nalezen, je již považován za standard a výčet pokračuje od aktuální pozice po konec pole. Ve výsledku je minimální (nebo maximální) hodnota v této skupině prvek, který byl naposledy rozpoznán jako standard.
