Suchen ist eine alltaegliche Aufgabe in der Informatik â ob in einer Datenbank, einer Datei oder einer Liste. Die Wahl des richtigen Suchalgorithmus beeinflusst, wie schnell ein Programm das gesuchte Element findet.
Lineare Suche
Die lineare Suche (auch sequentielle Suche) geht jedes Element einer Liste nacheinander durch, bis das gesuchte Element gefunden wird oder das Ende der Liste erreicht ist.
def lineare_suche(liste, ziel):
for i in range(len(liste)):
if liste[i] == ziel:
return i # Position gefunden
return -1 # Nicht gefunden
Beispiel: Suche nach 7 in [3, 9, 7, 1, 5]:
- Pruefe 3 â nein
- Pruefe 9 â nein
- Pruefe 7 â ja! Position 2 gefunden.
Die lineare Suche hat eine Zeitkomplexitaet von O(n). Im schlimmsten Fall muss sie alle n Elemente pruefen. Sie funktioniert auf unsortierten und sortierten Listen.
Binaere Suche
Die binaere Suche arbeitet nur auf sortierten Listen. Sie vergleicht das gesuchte Element mit dem mittleren Element der Liste und entscheidet, in welcher Haelfte weitergesucht wird.
Suche 7 in [1, 3, 5, 7, 9, 11, 13]:
Mitte: 7 -> Gefunden! Position 3.
Suche 3 in [1, 3, 5, 7, 9, 11, 13]:
Mitte (7): 3 < 7 -> Suche in linker Haelfte [1, 3, 5]
Mitte (3): Gefunden! Position 1.
Binaere Suche funktioniert nur auf sortierten Listen. Wenn die Liste unsortiert ist, liefert sie falsche Ergebnisse oder findet das Element nicht.
Vergleich: Wann welches verwenden?
| Situation | Empfohlener Algorithmus |
|---|---|
| Liste ist unsortiert | Lineare Suche |
| Liste ist sortiert, einmalige Suche | Binaere Suche |
| Sehr kleine Liste (unter 10 Elemente) | Lineare Suche |
| Grosse sortierte Liste | Binaere Suche |
Die binaere Suche hat eine Zeitkomplexitaet von O(log n). Bei einer Liste mit 1000 Elementen benoetigt sie hoechstens 10 Vergleiche â die lineare Suche bis zu 1000.
Die binaere Suche ist einer der effizientesten grundlegenden Algorithmen. Das Prinzip â halbiere immer den Suchbereich â ist ein Paradebeispiel fuer das Konzept "Teile und Herrsche".
Ăbungsaufgaben
Wie viele Schritte benoetigt die binaere Suche im schlimmsten Fall fuer eine Liste mit 16 Elementen?