Co je lineární vyhledávání?

Question

Accepted Answer

**Lineární vyhledávání** skenuje kolekci prvek po prvku, dokud nenajde cíl nebo nedosáhne konce. Funguje na **libovolném** seznamu — seřazeném či neseřazeném — ale běží v čase **O(n)**.

## Princip

Žádné předpoklady o pořadí: pouze kontrolujeme jednotlivé prvky jeden po druhém.

## Příklad

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Složitost

- **Čas:** O(n) v nejhorším případě (cíl poslední nebo chybí), O(1) v nejlepším případě.
- **Prostor:** O(1).

## Kdy použít

- Data jsou **neseřazená** a nemůžete si je dovolit seřadit.
- Seznam je malý, takže O(n) je zanedbatelné.
- Potřebujete jednorázové vyhledávání, kde není vytváření indexu nebo třídění prvním krokem.

Pokud hledáte opakovaně, preferujte seřazené pole s binárním vyhledáváním nebo hash set pro O(1) průměrné vyhledávání.

## Proč je to důležité

Lineární vyhledávání je základní měřítko, vůči kterému se měří všechny ostatní vyhledávací algoritmy.

Zpomíná vám, že *správný* algoritmus závisí na datech: neseřazená a malá data upřednostňují jednoduché skenování; velká a opakovaně dotazovaná data upřednostňují chytřejší struktury.

Znalost toho, kdy je O(n) dostatečné, zabraňuje předčasné optimalizaci.