Shrnutí na Lineární a binární vyhledávání

## Úvod do vyhledávání dat Vyhledávání dat je jednou z nejčastějších operací v informatice. Představte si, že máte seznam jmen, čísel nebo jakýchkoli jiných informací a potřebujete v něm najít konkrétní položku. Existuje mnoho způsobů, jak to udělat, a efektivita zvoleného přístupu může mít zásadní vliv na rychlost a výkon počítačového programu, zejména při práci s velkým množstvím dat. V tomto článku se zaměříme na dva základní a široce používané vyhledávací algoritmy: **lineární vyhledávání** a **binární vyhledávání**. Každý z těchto algoritmů má své specifické vlastnosti, výhody a nevýhody, a je vhodný pro různé situace. Pochopení jejich principů je klíčové pro každého, kdo se zabývá programováním nebo analýzou dat. > ### Co je to vyhledávací algoritmus? > Vyhledávací algoritmus je metoda, která se používá k nalezení konkrétní položky (prvku) v datové struktuře, jako je například seznam nebo pole. Cílem je zjistit, zda prvek existuje, a pokud ano, vrátit jeho pozici. ## Lineární vyhledávání (sekvenční vyhledávání) Lineární vyhledávání, známé také jako sekvenční vyhledávání, je nejjednodušší vyhledávací algoritmus. Jeho princip je velmi přímočarý: prochází seznamem prvek po prvku od začátku až do konce, dokud nenajde hledanou položku nebo dokud nedojde na konec seznamu. Pokud je položka nalezena, algoritmus vrátí její pozici (index). Pokud není nalezena, signalizuje to. ### Princip lineárního vyhledávání 1. Začněte u prvního prvku v seznamu. 2. Porovnejte aktuální prvek s hledanou hodnotou. 3. Pokud se shodují, vyhledávání je úspěšné a vrátí se pozice prvku. 4. Pokud se neshodují, přejděte na další prvek v seznamu. 5. Opakujte kroky 2-4, dokud není prvek nalezen nebo dokud nejsou prohledány všechny prvky v seznamu. ### Podmínka seřazení dat Pro lineární vyhledávání **není nutné**, aby data v seznamu byla seřazena. Funguje stejně dobře na seřazených i neseřazených datech. To je jeho hlavní výhoda v jednoduchosti implementace a univerzálnosti. ### Počet kroků a časová složitost Počet kroků, které lineární vyhledávání provede, závisí na velikosti seznamu a na pozici hledaného prvku. V nejlepším případě (hledaný prvek je hned první) provede algoritmus pouze jedno porovnání. V nejhorším případě (prvek je poslední nebo není v seznamu vůbec) musí prohledat celý seznam. Pokud má seznam $n$ prvků, provede až $n$ porovnání. Časová složitost lineárního vyhledávání se vyjadřuje pomocí notace Big O jako **O(n)**. To znamená, že doba běhu algoritmu roste lineárně s počtem prvků $n$ v seznamu. Pokud zdvojnásobíte velikost seznamu, přibližně se zdvojnásobí i doba potřebná k vyhledání prvku (v průměrném a nejhorším případě). Zajímavost: Lineární vyhledávání je často výchozí metodou, kterou lidé podvědomě používají při hledání něčeho v neseřazeném seznamu, například jména v telefonním seznamu bez abecedního uspořádání. ### Příklad lineárního vyhledávání Předpokládejme, že máme neseřazený seznam čísel: $[5, 12, 3, 8, 1, 10]$ a hledáme číslo $8$. 1. Porovnáme $8$ s $5$ (na pozici 0). Neshoda. 2. Porovnáme $8$ s $12$ (na pozici 1). Neshoda. 3. Porovnáme $8$ s $3$ (na pozici 2). Neshoda. 4. Porovnáme $8$ s $8$ (na pozici 3). **Shoda!** Algoritmus vrací pozici $3$. Pokud bychom hledali číslo $7$: 1. Porovnáme $7$ s $5$. Neshoda. 2. Porovnáme $7$ s $12$. Neshoda. 3. Porovnáme $7$ s $3$. Neshoda. 4. Porovnáme $7$ s $8$. Neshoda. 5. Porovnáme $7$ s $1$. Neshoda. 6. Porovnáme $7$ s $10$. Neshoda. 7. Seznam je prohledán celý. Číslo $7$ nebylo nalezeno. ## Binární vyhledávání Binární vyhledávání je mnohem efektivnější algoritmus než lineární vyhledávání, ale má jednu klíčovou podmínku: **data v seznamu musí být seřazena** (vzestupně nebo sestupně). Jeho princip spočívá v opakovaném dělení prohledávané části seznamu na poloviny. ### Princip binárního vyhledávání 1. Určete střední prvek aktuálně prohledávané části seznamu. 2. Porovnejte hledanou hodnotu se středním prvkem. 3. Pokud se shodují, vyhledávání je úspěšné a vrátí