Vad är linjär sökning?

Question

Accepted Answer

**Linjär sökning** skannar en samling element för element tills den hittar målet eller når slutet. Det fungerar på **någon** lista — sorterad eller inte — men körs på **O(n)** tid.

## Idén

Ingen antaganden om ordning: bara kontrollera varje objekt ett i taget.

## Exempel

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

## Komplexitet

- **Tid:** O(n) värsta fall (målet sist eller frånvarande), O(1) bästa fall.
- **Utrymme:** O(1).

## När ska man använda det

- Data är **osorterad** och du kan inte sortera den.
- Listan är liten, så O(n) är försumbar.
- Du behöver en engångssökning där att bygga ett index eller sortera först inte är värt det.

Om du söker upprepade gånger, föredra en sorterad array med binär sökning eller en hash-set för O(1) genomsnittliga sökningar.

## Varför det är viktigt

Linjär sökning är utgångspunkten som alla andra sökningar mäts mot.

Det påminner dig om att *rätt* algoritm beror på data: osorterad och liten gynnar den enkla genomsökningen; stor och upprepat frågad gynnar smartare strukturer.

Att veta när O(n) är tillräckligt bra förhindrar för tidig optimering.