Hvad er lineær søgning?

Question

Accepted Answer

**Lineær søgning** scanner en samling element for element, indtil den finder målet eller når slutningen. Den fungerer på **enhver** liste — sorteret eller ej — men kører i **O(n)** tid.

## Idéen

Ingen antagelser om rækkefølge: tjek blot hvert element en ad gangen.

## Eksempel

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

## Kompleksitet

- **Tid:** O(n) worst case (målet sidst eller fraværende), O(1) best case.
- **Plads:** O(1).

## Hvornår skal det bruges

- Dataene er **usorterede** og du har ikke råd til at sortere dem.
- Listen er lille, så O(n) er ubetydelig.
- Du har brug for et engangssøgning, hvor det ikke er værd at bygge et indeks eller sortere først.

Hvis du søger gentagne gange, foretrækker du en sorteret array med binær søgning eller et hash set for O(1) gennemsnitlige opslag.

## Hvorfor det betyder noget

Lineær søgning er basislinje, som alle andre søgninger måles mod.

Det minder dig om, at den *rigtige* algoritme afhænger af dataene: usorteret og tiny favoriserer den simple scan; stor og gentagne gange forespurgt favoriserer smartere strukturer.

At vide, hvornår O(n) er godt nok, forhindrer for tidlig optimering.