Što je linearno pretraživanje?

Question

Accepted Answer

**Linear search** skenira zbirku element po element dok ne naiđe na cilj ili se ne dostigne kraj. Radi na **bilo kojoj** listi — sortiranoj ili ne — ali se izvršava u **O(n)** vremenu.

## Ideja

Bez pretpostavki o redoslijedu: samo provjerite jedan po jedan element.

## Primjer

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

- **Vrijeme:** O(n) najgora slučaj (cilj zadnji ili odsutan), O(1) najbolji slučaj.
- **Prostor:** O(1).

## Kada koristiti

- Podaci su **nesortirani** i ne možete ih sortirati.
- Popis je mali, pa je O(n) zanemarivo.
- Trebate jednokratno pretraživanje gdje stvaranje indeksa ili sortiranje prvo nije vrijedno.

Ako ste često pretraživali, preferirajte sortirani niz s binarnim pretraživanjem ili hash skup za O(1) prosječno pretraživanja.

## Zašto je to važno

Linearno pretraživanje je osnovna vrijednost prema kojoj se mjere sva ostala pretraživanja.

Podsjeća vas da *pravi* algoritam ovisi o podacima: nesortirani i mali favoriziraju jednostavno skeniranje; veliki i često upitan favoriziraju pametnije strukture.

Znanje kada je O(n) dovoljno sprječava preuranu optimizaciju.