Mit Google fortfahren
Suchalgorithmus: Linear oder binär suchen
Ein Suchalgorithmus ist eine eindeutige Schrittfolge, mit der du ein bestimmtes Element in einer Datenmenge findest oder feststellst, dass es fehlt. Welche Suche passt, hängt vor allem davon ab, ob die Daten sortiert sind: Die lineare Suche funktioniert immer, die schnellere binäre Suche braucht eine sortierte Liste.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was tut ein Suchalgorithmus?
Stell dir eine Liste mit Spielernamen vor. Die Eingabe besteht aus der Liste und dem gesuchten Namen. Der Algorithmus prüft nach festgelegten Regeln Listenelemente. Seine Ausgabe ist entweder die Fundstelle oder die Aussage „nicht enthalten“.
Suchalgorithmus
Ein Suchalgorithmus ist ein Verfahren, das Daten systematisch nach einem Zielwert durchsucht. Jeder Vergleich fragt: „Ist dieses Element der Zielwert?“ Je nach Verfahren entscheidet das Ergebnis auch, wo weitergesucht wird.
Für die Wahl des Verfahrens sind drei Fragen wichtig:
- Sind die Daten sortiert?
- Wie groß ist die Datenmenge?
- Lohnt sich der Aufwand, die Daten vor der Suche zu sortieren?
Ein schnelles Verfahren ist nur dann passend, wenn seine Voraussetzungen erfüllt sind. Binäre Suche auf einer ungeordneten Liste kann Treffer übersehen.
Lineare Suche prüft der Reihe nach
Die lineare Suche beginnt beim ersten Element. Sie vergleicht jedes Element mit dem Ziel und stoppt beim ersten Treffer. Erreicht sie das Listenende ohne Treffer, ist das Ziel nicht enthalten. Die Reihenfolge der Daten spielt keine Rolle.
Gesucht ist 34 in der Liste
[3, 7, 11, 14, 18, 23, 29, 34, 41, 47, 52].
Die Vergleiche lauten der Reihe nach: 3, 7, 11, 14, 18, 23, 29, 34. Der achte Vergleich trifft. Die Ausgabe ist also: „34 steht an Position 8“, wenn ab 1 gezählt wird.
Ist der Zielwert das erste Element, genügt ein Vergleich. Fehlt er oder steht er ganz am Ende, werden bei einer Liste mit $n$ Elementen bis zu $n$ Vergleiche benötigt. Deshalb beschreibt man das lineare Wachstum der Laufzeit mit $O(n)$: Verdoppelt sich die Listenlänge, kann sich auch die maximale Zahl der Vergleiche ungefähr verdoppeln.
Binäre Suche halbiert den Suchbereich
Die binäre Suche nutzt die Ordnung einer aufsteigend sortierten Liste. Sie vergleicht das Ziel mit einem mittleren Element. Ist das Ziel kleiner, bleibt nur der linke Teil; ist es größer, bleibt nur der rechte Teil. So wird der noch mögliche Suchbereich immer wieder ungefähr halbiert.
Gesucht ist wieder 34 in der sortierten Liste
[3, 7, 11, 14, 18, 23, 29, 34, 41, 47, 52].
- Mitte 23: $34 > 23$. Nur
[29, 34, 41, 47, 52]bleibt. - Mitte 41: $34 < 41$. Nur
[29, 34]bleibt. - Bei zwei Elementen wird hier die linke Mitte 29 gewählt: $34 > 29$.
- Das verbleibende Element 34 ist der Treffer.
Die binäre Suche benötigt vier Vergleiche statt acht bei der linearen Suche. Eine andere feste Regel für die Mitte bei zwei Elementen kann die Zahl im Einzelfall ändern, aber nicht das Halbierungsprinzip.
Warum darfst du eine Hälfte verwerfen? In einer sortierten Liste sind alle Werte links von 41 kleiner als 41 und alle Werte rechts davon größer. Wenn 34 kleiner als 41 ist, kann es rechts nicht stehen. Diese Aussage bleibt nach jedem Schritt für den aktuellen Suchbereich gültig.
Bei $n$ Elementen wächst die maximale Zahl der Vergleiche ungefähr logarithmisch, geschrieben $O(\log n)$. Bei 1024 Elementen führen zehn Halbierungen von 1024 auf einen Kandidaten, denn $2^{10}=1024$. In einer üblichen Umsetzung sind im ungünstigsten Fall höchstens 11 Zielvergleiche nötig, einschließlich der abschließenden Prüfung des letzten Kandidaten.
Aufwand vergleichen und passend wählen
Die Anzahl der Vergleiche zeigt, wie stark ein Verfahren mit der Eingabegröße wächst. Für eine einzelne kleine Liste kann der Unterschied gering sein. Bei großen Listen wird das wiederholte Halbieren deutlich wirksamer.
| Anzahl Elemente | Lineare Suche: höchstens | Binäre Suche: höchstens ungefähr |
|---|---|---|
| 16 | 16 Vergleiche | 5 Vergleiche |
| 128 | 128 Vergleiche | 8 Vergleiche |
| 1024 | 1024 Vergleiche | 11 Vergleiche |
Die Werte der binären Suche zählen eine abschließende Zielprüfung mit. Die genaue Zahl hängt von der Umsetzung und davon ab, ob der Treffer vorhanden ist. Entscheidend ist das Wachstum: linear bei $O(n)$, logarithmisch bei $O(\log n)$.
Vertiefung: Big O beschreibt hier, wie der Aufwand bei großen Eingaben wächst. Die Notation ist keine Stoppuhr. Konstanten, Datenstruktur und Zugriffskosten beeinflussen die tatsächliche Laufzeit. Außerdem kostet das Sortieren selbst Zeit. Für eine einzige Suche in ungeordneten Daten kann lineares Suchen sinnvoller sein als erst zu sortieren. Bei vielen Suchen kann sich eine einmalige Sortierung lohnen.
Eine sichere Entscheidungshilfe:
- Unsortiert und nur wenige Suchen: lineare Suche.
- Bereits sortiert und direkter Zugriff auf mittlere Elemente möglich: binäre Suche.
- Unsortiert und viele spätere Suchen: Kosten des Sortierens gegen die Einsparungen bei den Suchen abwägen.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Suchalgorithmus
- Eingabe und Ausgabe
- Liste plus Zielwert
- Fundstelle oder „nicht enthalten“
- Lineare Suche
- der Reihe nach prüfen
- Sortierung nicht nötig
- Aufwand $O(n)$
- Binäre Suche
- Mitte vergleichen
- sortierte Liste nötig
- Aufwand $O(\log n)$
- Entscheidung
- Voraussetzungen prüfen
- Such- und Vorbereitungskosten vergleichen
- Eingabe und Ausgabe