Kaj je linearno iskanje?

Question

Accepted Answer

**Linearno iskanje** pregleda zbirko element za elementom, dokler ne najde cilja ali ne doseže konca. Deluje na **kateremkoli** seznamu — sortiranem ali ne — vendar se izvaja v **O(n)** času.

## Ideja

Brez predpostavk o vrstnem redu: preprosto preveri vsak element enega za drugim.

## Primer

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

## Časovna zahtevnost

- **Čas:** O(n) v najslabšem primeru (cilj je zadnji ali odsoten), O(1) v najboljšem primeru.
- **Prostor:** O(1).

## Kdaj uporabiti

- Podatki so **nesortirani** in jih ne morete dovolj hitro sortirati.
- Seznam je majhen, zato je O(n) zanemarljiv.
- Potrebujete enkratno iskanje, pri katerem gradnja indeksa ali sortiranje nista vredna truda.

Če iščete večkrat, raje uporabite sortirano polje z binarnim iskanjem ali hash nabor za povprečne iskane v O(1).

## Zakaj je to pomembno

Linearno iskanje je osnovni primer, ki se ga uporabljajo kot merilo za vsa ostala iskanja.

Opominja vas, da je *pravilni* algoritem odvisen od podatkov: nesortirani in majhni podatki so primerni za enostavno presegovanje; veliki in večkrat napovedovani podatki pa zahtevajo pametnejše strukture.

Znanje, kdaj je O(n) dovolj dobro, preprečuje prezgodnjo optimizacijo.