Lineare Suche
# Lineare Suche

Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt.

Die Aufgabe besteht darin, ein Element in einer Liste oder einem Array mit n Elementen zu finden. Man geht dazu die Liste Element für Element durch, bis man es gefunden hat. Der Suchaufwand wächst linear mit der Anzahl der Elemente in der Liste.

Die effizientere Binäre Suche kann nur bei geordneten Listen benutzt werden.

Für ungeordnete Listen existiert mit Lazy Select noch ein randomisierter Algorithmus, der mit relativ hoher Wahrscheinlichkeit das x-te Element einer Liste bezüglich einer Ordnung schneller als in linearer Zeit finden kann.

## Komplexität

Die lineare Suche befindet sich in der Komplexitätsklasse O(n), da sie im schlechtesten Fall (wenn der gesuchte Wert nicht gefunden werden kann) n Vergleiche benötigt.

Wenn die Daten zufallsverteilt sind, dann werden im Schnitt (n+1)/2 Vergleichsoperationen benötigt.

Im besten Fall ist gleich das erste Element der Liste dasjenige, das man sucht.

Wenn die Anzahl der Elemente in einer Liste klein ist, dann ist es oft auch das effizienteste Verfahren.

## Implementierungen (Beispiele)

### Beispielimplementierung in Java

Das Beispiel gibt den Wert -1 zurück, wenn das gesuchte Element nicht im Array daten vorhanden ist. Ansonsten gibt es die Position des Elementes zurück.

### Beispielimplementierung in Python

Findet alle Suchschlüssel in der Liste.

Findet erstes Vorkommen des Suchschlüssels in einer Liste.

### Beispielimplementierung in C

Findet ersten Suchschlüssel (Ganzzahl) in der Liste.

