Mikä on lineaarinen haku?

Question

Accepted Answer

**Lineaarinen haku** skannaa kokoelmaa alkio kerrallaan, kunnes se löytää kohteen tai saavuttaa lopun. Se toimii **mihin tahansa** listaan — järjestettyyn tai järjestämättömään — mutta toimii **O(n)** ajassa.

## Idea

Ei oletuksia järjestyksestä: tarkista vain jokainen alkio yksi kerrallaan.

## Esimerkki

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

## Monimutkaisuus

- **Aika:** O(n) pahimmassa tapauksessa (kohde lopussa tai poissa), O(1) parhaassa tapauksessa.
- **Tila:** O(1).

## Milloin käyttää

- Tiedot ovat **järjestämättömät** ja sinulla ei ole varaa järjestää niitä.
- Lista on pieni, joten O(n) on merkityksetön.
- Tarvitset kertakäyttöisen haun, jossa indeksin rakentaminen tai järjestäminen etukäteen ei ole sen arvoista.

Jos teet hakuja toistuvasti, suosi järjestettyä taulukkoa binaarihakulla tai hajautussarjaa O(1) keskimääräisille hauille.

## Miksi se on tärkeää

Lineaarinen haku on perusviite, johon kaikkia muita hakuja verrataan.

Se muistuttaa sinua siitä, että *oikea* algoritmi riippuu tiedoista: järjestämätön ja pieni suosii yksinkertaista skannausta; suuri ja toistuvasti käytetty suosii älykkäämpiä rakenteita.

Tietäminen, milloin O(n) on riittävän hyvä, estää ennenaikaista optimointia.