Algorithmen
Suchalgorithmen – Linear und Binär
Diese Seite behandelt die grundlegenden Suchalgorithmen Lineare Suche und Binäre Suche mit Erklärungen, Pseudocode und Laufzeitanalyse.
Suchalgorithmen
Lineare Suche
Die lineare Suche (engl. linear search oder sequential search) durchläuft eine Liste Element für Element, bis das gesuchte Element gefunden wurde oder das Ende erreicht ist.
Eigenschaften:
- Einfach zu implementieren
- Funktioniert mit unsortierten Listen
- Laufzeit: O(n)
Pseudocode:
function lineareSuche(liste, ziel):
für jedes element in liste:
wenn element == ziel:
return position
return -1 // nicht gefunden
Binäre Suche
Die binäre Suche (engl. binary search) ist effizienter, setzt aber eine sortierte Liste voraus. Sie halbiert wiederholt den Suchbereich.
Eigenschaften:
- Schnell bei großen, sortierten Datenmengen
- Voraussetzung: sortierte Liste
- Laufzeit: O(log n)
Pseudocode:
function binaereSuche(liste, ziel):
links = 0
rechts = liste.länge - 1
solange links ≤ rechts:
mitte = (links + rechts) / 2
wenn liste[mitte] == ziel:
return mitte
sonst wenn liste[mitte] < ziel:
links = mitte + 1
sonst:
rechts = mitte - 1
return -1 // nicht gefunden
Vergleich
| Kriterium | Lineare Suche | Binäre Suche |
|---|---|---|
| Voraussetzung | Keine | Sortierte Liste |
| Laufzeit | O(n) | O(log n) |
| Implementierung | Einfach | Etwas komplexer |
Typische Prüfungsfragen
- Was ist der Unterschied zwischen linearer und binärer Suche?
- Welche Voraussetzung muss für die binäre Suche erfüllt sein?
- Wann ist die lineare Suche sinnvoller als die binäre?