Hva er lineært søk?

Question

Hva er lineært søk?

Accepted Answer

**Lineært søk** skanner en samling element for element inntil det finner målet eller når slutten. Det fungerer på **enhver** liste — sortert eller ikke — men kjører i **O(n)** tid.

## Ideen

Ingen antagelser om rekkefølge: bare sjekk hvert element en etter en.

## 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ål sist eller fraværende), O(1) best case.
- **Plass:** O(1).

## Når du skal bruke det

- Dataene er **usortert** og du kan ikke sortere det.
- Listen er liten, så O(n) er ubetydelig.
- Du trenger et engangslookup der bygging av indeks eller sortering først ikke er verdt det.

Hvis du søker gjentatte ganger, foretrekk en sortert array med binary search eller en hash set for O(1) gjennomsnittlige oppslag.

## Hvorfor det er viktig

Lineært søk er grunnlinjen som alle andre søk måles mot.

Det minner deg på at *riktig* algoritme avhenger av dataene: usortert og lite favoriserer den enkle skanningen; stor og gjentatt forespurt favoriserer smartere strukturer.

Å vite når O(n) er god nok, forhindrer prematur optimalisering.