Suchen: linear vs. binär

Eines der häufigsten Probleme in der Programmierung: in einer Liste nach einem bestimmten Wert suchen. „Ist der Name Müller in der Mitarbeiterliste?" – „An welcher Position in dieser sortierten Tabelle steht die Zahl 42?" – „Existiert dieser Benutzername schon in der Datenbank?" All das sind Such-Probleme.

Es gibt viele Such-Algorithmen, aber zwei davon sind absolut grundlegend und tauchen ständig auf: die lineare Suche (auch sequenzielle Suche genannt) und die binäre Suche. Sie zeigen schön, wie ein cleverer Algorithmus dramatisch schneller sein kann als ein naiver – wenn man bestimmte Vorbedingungen erfüllt.

1) Die lineare Suche – einfach und universell

Die simpelste Methode: gehe alle Elemente der Liste durch, vom ersten bis zum letzten, und vergleiche jedes mit dem Suchwert. Wenn du es findest – fertig. Wenn du am Ende angekommen bist und nichts gefunden hast – auch fertig, aber mit „nicht da"-Antwort.

Das Analoge im Alltag: du suchst deinen Autoschlüssel auf einem unaufgeräumten Schreibtisch. Du gehst alles durch, Stück für Stück, bis du ihn findest – oder am Ende feststellst, dass er nicht da ist. Keine Sortierung, keine Vorbedingung, einfach durchschauen.

2) Lineare Suche in Pseudocode

Die Implementierung ist erfreulich kurz. Hier in Pseudocode als Schleife mit Verzweigung:

Die Konvention: bei „nicht gefunden" wird -1 zurückgegeben, weil das keine gültige Position sein kann (Positionen sind 1- oder 0-basiert, aber nie negativ). Andere Sprachen verwenden auch null oder Spezialwerte. Java z.B. gibt bei indexOf() ebenfalls -1 zurück.

3) Die binäre Suche – Halbieren statt Durchgehen

Wenn die Liste sortiert ist, geht es viel schneller. Statt vom Anfang an alles durchzugehen, schaust du in die Mitte. Drei mögliche Fälle:

• Mittelwert = Ziel? → gefunden, fertig.
• Mittelwert > Ziel? → das Ziel muss links liegen. Rechte Hälfte ignorieren.
• Mittelwert < Ziel? → das Ziel muss rechts liegen. Linke Hälfte ignorieren.

Wiederhole das mit der verbleibenden Hälfte, bis du das Ziel findest oder die Hälfte leer ist. Das ist die binäre Suche. „Binär" weil in jedem Schritt zwei Möglichkeiten – links oder rechts.

Klassische Analogie: du suchst einen Namen im Telefonbuch (in einem alten, aus Papier!). Du schlägst nicht auf Seite 1 auf und blätterst durch. Du schlägst in der Mitte auf, schaust ob dein Name vor oder nach diesem Buchstaben liegt, und ignorierst die andere Hälfte. So halbierst du in jedem Schritt deinen Suchbereich.

4) Binäre Suche in Pseudocode

Die Implementierung ist etwas länger, aber nicht kompliziert. Wichtig: vor dem Aufruf muss die Liste sortiert sein. Wir merken uns linken und rechten Rand des aktuellen Suchbereichs:

Binäre Suche lässt sich auch elegant rekursiv schreiben: man ruft sich selbst auf der kleineren Hälfte auf. Beide Varianten sind funktional gleichwertig.

5) Warum binär so viel schneller ist

In jedem Schritt halbiert sich der Suchbereich. Bei einer Liste mit n Elementen brauchen wir maximal so viele Schritte, wie wir n halbieren können, bis 1 übrig bleibt. Das ist der Logarithmus zur Basis 2, kurz log₂(n). Zum Vergleich:

6) Halbierungs-Prinzip visualisiert

Das exponentielle Schrumpfen des Suchbereichs sieht man besonders gut, wenn man es visualisiert. Hier wird in jedem Schritt der Suchbereich halbiert – bei 1024 Startgröße sind wir nach 10 Schritten bei 1 angekommen:

7) Direkter Vergleich: lineare vs. binäre Suche

Beide Algorithmen lösen dasselbe Problem – aber unter unterschiedlichen Voraussetzungen und mit unterschiedlichen Eigenschaften:

8) Weitere Such-Strategien (Ausblick)

Lineare und binäre Suche sind nicht die einzigen Verfahren. Für spezielle Szenarien gibt es schnellere Methoden. Sie spielen in IHK-Prüfungen meist nur am Rand eine Rolle, aber gut zu wissen, dass sie existieren:

• Hash-basierte Suche: in einer Hash-Map findest du Werte in O(1) – konstante Zeit, unabhängig von der Größe. Das geht, weil über eine Hash-Funktion direkt die Position berechnet wird. Trade-off: zusätzlicher Speicherbedarf.
• Baum-Suche: in einem balancierten Suchbaum (z.B. AVL-Baum, Rot-Schwarz-Baum) ist die Suche ebenfalls O(log n). Vorteil gegenüber sortiertem Array: Einfügen und Löschen sind ebenfalls schnell.
• Datenbank-Indizes: SQL-Datenbanken legen B-Bäume an, um Such-Abfragen in O(log n) zu beantworten. Siehe K36 Lektion zu Datenbankindizes.
• Interpolations-Suche: Variante der binären Suche, die nicht in der Mitte schaut, sondern an einer „klugen" Position basierend auf dem Wertebereich. In günstigen Fällen O(log log n), aber instabil.

9) Häufige Klausur-Fallen

Das Thema „Suchen" wird in IHK-Klausuren regelmäßig abgefragt. Typische Fragen und ihre Stolperfallen:

• „Wie viele Vergleiche im Worst Case?" Lineare Suche: n. Binäre Suche: ⌈log₂(n)⌉, also Logarithmus aufgerundet. Bei n = 1000 sind das 10. Bei n = 100 sind es 7.
• „Funktioniert binäre Suche auf einer unsortierten Liste?" Nein! Die Sortierung ist Voraussetzung. Ohne sie liefert der Algorithmus falsche Ergebnisse (nicht etwa langsam – einfach falsch).
• „Wann ist lineare Suche besser?" Bei kleinen Listen (Konstanten-Overhead), bei verketteten Listen ohne wahlfreien Zugriff, wenn die Liste sowieso nur einmal durchgegangen wird.
• Off-by-one in der Mitte-Berechnung: mitte = (links + rechts) / 2 bei Ganzzahl-Division. Achtung bei sehr großen Zahlen: links + rechts kann Integer-Overflow erzeugen – professionelle Implementierungen schreiben deshalb links + (rechts - links) / 2.
• Falsche Anpassung der Pointer: links = mitte + 1 bzw. rechts = mitte - 1 – nicht einfach links = mitte, sonst kann eine Endlosschleife entstehen.

Zusammenfassung

Zwei grundlegende Such-Algorithmen, die jeder Informatiker beherrschen muss. Lineare Suche: alle Elemente von vorne durchgehen, mit dem Ziel vergleichen. Funktioniert immer – ohne Vorbedingungen. Komplexität: O(n) im Worst Case. Binäre Suche: in jedem Schritt die Mitte des verbleibenden Bereichs prüfen und die Hälfte mit dem Ziel weiter durchsuchen. Voraussetzung: Liste muss sortiert sein. Komplexität: O(log n) – also dramatisch schneller bei großen Listen. Bei 1 Million Elementen: ~20 Vergleiche statt 1 Million. Die magische Eigenschaft der binären Suche: Verdopplung der Listengröße kostet nur einen zusätzlichen Vergleich. Das ist die exponentielle Wirkung des Logarithmus. Wann lohnt sich was? Binäre Suche nur, wenn die Liste sowieso sortiert ist oder oft durchsucht wird – sonst kostet das Sortieren mehr als die Linear-Suche. Lineare Suche ist auch nötig auf Datenstrukturen ohne wahlfreien Zugriff (verkettete Listen). Praktische Anwendungen der binären Suche: Datenbank-Indizes, Telefonbücher, Auto-Vervollständigung, Versions-Kontrollsysteme (git bisect). Stolperfallen: Vergessen dass Sortierung Voraussetzung ist, Off-by-one bei der Mitte-Berechnung, falsche Pointer-Anpassung. Es geht noch schneller: Hash-basiert in O(1), oder über balancierte Bäume. Die nächste Lektion zeigt, wie man eine Liste sortiert: Sortier-Algorithmen – mit verschiedenen Strategien und Komplexitäten.