Was ist Linearsuche?

Question

Accepted Answer

**Linearsuche** scannt eine Kollektion Element für Element, bis sie das Ziel findet oder das Ende erreicht. Sie funktioniert auf **jeder** Liste – sortiert oder nicht – läuft aber in **O(n)** Zeit.

## Die Idee

Keine Annahmen über die Reihenfolge: einfach jedes Element nacheinander prüfen.

## Beispiel

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

## Komplexität

- **Zeit:** O(n) Worst Case (Ziel am Ende oder nicht vorhanden), O(1) Best Case.
- **Speicher:** O(1).

## Wann man sie einsetzt

- Die Daten sind **unsortiert** und Sie können sie sich nicht leisten zu sortieren.
- Die Liste ist klein, sodass O(n) vernachlässigbar ist.
- Sie benötigen eine einmalige Suche, bei der das Aufbauen eines Index oder vorheriges Sortieren sich nicht lohnt.

Wenn Sie wiederholt suchen, bevorzugen Sie ein sortiertes Array mit Binärsuche oder eine Hash-Menge für O(1) durchschnittliche Zugriffe.

## Warum es wichtig ist

Linearsuche ist die Basislinie, an der alle anderen Suchalgorithmen gemessen werden.

Sie erinnert Sie daran, dass der *richtige* Algorithmus von den Daten abhängt: unsortiert und winzig begünstigt den einfachen Scan; groß und wiederholt abgefragt begünstigt intelligentere Strukturen.

Zu wissen, wann O(n) ausreichend ist, verhindert vorzeitige Optimierung.