Wat is linear search?

Question

Accepted Answer

**Linear search** scant een verzameling element voor element totdat het het doel vindt of het einde bereikt. Het werkt op **elke** lijst — gesorteerd of niet — maar loopt in **O(n)** tijd.

## Het idee

Geen aannames over volgorde: controleer gewoon elk item één voor één.

## Voorbeeld

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

## Complexiteit

- **Tijd:** O(n) worst case (doel laatste of afwezig), O(1) best case.
- **Ruimte:** O(1).

## Wanneer te gebruiken

- De gegevens zijn **ongesorteerd** en u kunt het niet sorteren.
- De lijst is klein, dus O(n) is verwaarloosbaar.
- U hebt een eenmalige zoeking waarbij het bouwen van een index of sorteren niet de moeite waard is.

Als u herhaaldelijk zoekt, geeft u de voorkeur aan een gesorteerde array met binary search of een hash set voor O(1) gemiddelde zoekresultaten.

## Waarom het belangrijk is

Linear search is de baseline waaraan alle andere zoekopdrachten worden gemeten.

Het herinnert u eraan dat het *juiste* algoritme afhangt van de gegevens: ongesorteerd en klein begunstigt de eenvoudige scan; groot en herhaaldelijk bevraagd begunstigt slimmere structuren.

Weten wanneer O(n) goed genoeg is, voorkomt voortijdige optimalisatie.