Co to jest wyszukiwanie liniowe?

Question

Accepted Answer

**Wyszukiwanie liniowe** skanuje kolekcję element po elemencie, aż znajdzie cel lub osiągnie koniec. Działa na **dowolnej** liście — posortowanej lub nie — ale działa w **O(n)** czasu.

## Pomysł

Brak założeń dotyczących kolejności: po prostu sprawdzaj każdy element jeden po drugim.

## Przykład

```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
```

## Złożoność

- **Czas:** O(n) najgorszy przypadek (cel ostatni lub nieobecny), O(1) najlepszy przypadek.
- **Przestrzeń:** O(1).

## Kiedy użyć

- Dane są **nieposortowane** i nie możesz ich posortować.
- Lista jest mała, więc O(n) jest znikome.
- Potrzebujesz jednorazowego wyszukiwania, gdzie budowanie indeksu lub sortowanie na początek nie warto.

Jeśli wyszukujesz wielokrotnie, preferuj posortowaną tablicę z binary search lub zestaw hash dla O(1) średniego wyszukiwania.

## Dlaczego to ważne

Wyszukiwanie liniowe jest punktem odniesienia, względem którego mierzy się wszystkie pozostałe wyszukiwania.

Przypomina ci, że *prawidłowy* algorytm zależy od danych: nieposortowane i małe faworyzują prostą skanowanie; duże i wielokrotnie pytane faworyzują inteligentniejsze struktury.

Wiedzenie, kiedy O(n) jest wystarczające, zapobiega przedwczesnej optymalizacji.