Ce este căutarea liniară?

Question

Accepted Answer

**Căutarea liniară** scanează o colecție element cu element până când găsește ținta sau ajunge la sfârșit. Funcționează pe **orice** listă — sortată sau nu — dar rulează în timp **O(n)**.

## Ideea

Fără presupuneri despre ordine: doar verifică fiecare element pe rând.

## Exemplu

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

## Complexitate

- **Timp:** O(n) caz cel mai rău (țintă ultima sau absentă), O(1) caz cel mai bun.
- **Spațiu:** O(1).

## Când să o folosești

- Datele sunt **nesortate** și nu poți să le sortezi.
- Lista este mică, deci O(n) este neglijabil.
- Ai nevoie de o căutare unică în care construirea unui index sau sortare în prealabil nu merită.

Dacă cauți în mod repetat, preferi un tablou sortat cu căutare binară sau un set hash pentru căutări medii O(1).

## De ce este important

Căutarea liniară este linia de bază împotriva căreia sunt măsurate toate celelalte căutări.

Îți amintește că *algoritmul corect* depinde de date: nesortate și mic favorizează scanarea simplă; mare și interogat în mod repetat favorizează structuri mai inteligente.

Știul când O(n) este suficient de bun previne optimizarea timpurie.