Suchalgorithmen — Linear, Binär, Hashing

Einführung

Du googelst etwas — und in 0,3 Sekunden durchsucht Google Milliarden von Webseiten. Dein Handy entsperrt sich per Fingerabdruck in Millisekunden, indem es dein Muster aus Millionen Einträgen herausfindet. Wie geht das?

Suchen ist eine der grundlegendsten Operationen in der Informatik. Und der Unterschied zwischen einem schlechten und einem guten Suchalgorithmus ist der Unterschied zwischen einer Antwort in einer Sekunde — und einer Antwort nach Stunden.

In dieser Lektion lernst du drei fundamentale Suchverfahren kennen, ihre Vor- und Nachteile, und siehst, wie sie in realen Systemen wie Datenbanken eingesetzt werden.

Grundidee

Alle Suchalgorithmen lösen dasselbe Problem: Finde ein Element in einer Datenmenge. Das Einzige, was sich unterscheidet, ist wie gesucht wird — und das beeinflusst dramatisch, wie viele Schritte nötig sind.

Bei 1 Million Elementen:

Lineare Suche: bis zu 1.000.000 Schritte
Binäre Suche: maximal 20 Schritte
Hashing: durchschnittlich 1 Schritt

Das ist der Grund, warum Algorithmuswahl kein akademisches Thema ist, sondern direkten Einfluss auf Performance hat.

Erklärung

Lineare Suche — O(n)

Idee: Gehe die Liste von vorne nach hinten durch, Element für Element, bis das gesuchte gefunden oder das Ende erreicht ist.

Pseudocode:

für i von 0 bis n-1:
  wenn liste[i] == ziel:
    gib i zurück
gib "nicht gefunden" zurück

Eigenschaften:

Keine Voraussetzungen — die Liste muss nicht sortiert sein.
Worst Case: Das Element ist ganz hinten oder nicht vorhanden → n Vergleiche → O(n).
Best Case: Das Element ist ganz vorne → 1 Vergleich → O(1).
Durchschnitt: n/2 Vergleiche → O(n).

Wann sinnvoll? Bei kleinen Listen, unsortierter Datenmenge, oder wenn die Suche nur einmal vorkommt. Für große Datenmengen inakzeptabel langsam.

Binäre Suche — O(log n)

Voraussetzung: Die Liste muss sortiert sein.

Idee: Schau immer in der Mitte nach. Ist das gesuchte Element kleiner als das mittlere? Dann liegt es in der linken Hälfte — ignoriere die rechte. Ist es größer? Rechte Hälfte. Wiederhole mit der verbliebenen Hälfte, bis das Element gefunden ist oder keine Hälfte mehr übrig ist.

Beispiel: Suche 7 in [1, 3, 5, 7, 9, 11, 13] (7 Elemente)

Schritt 1: Mitte = Index 3 = 7. Gefunden! 1 Schritt.

Schlechter Fall: Suche 13 in [1, 3, 5, 7, 9, 11, 13]

Schritt 1: Mitte = 7. 13 > 7 → rechte Hälfte [9, 11, 13]
Schritt 2: Mitte = 11. 13 > 11 → rechte Hälfte [13]
Schritt 3: Mitte = 13. Gefunden!

3 Schritte für 7 Elemente. Bei 1.000.000 Elementen: maximal 20 Schritte (log₂(1.000.000) ≈ 20).

Warum O(log n)? Bei jedem Schritt wird die Datenmenge halbiert. log₂(n) sagt, wie oft man n halbieren kann, bis man bei 1 ankommt. Das ist eine extrem langsam wachsende Funktion.

Implementierung: Iterativ (mit Zeigern für linkes und rechtes Ende) oder rekursiv.

Wann sinnvoll? Bei sortierten Arrays oder bei Daten, die einmal sortiert und viele Male durchsucht werden. Nicht geeignet für verkettete Listen (kein Indexzugriff).

Hashing — O(1) im Durchschnitt

Du kennst HashMaps aus der Datenstruktur-Lektion. Hashing als Suchmethode basiert darauf:

Idee: Eine Hashfunktion berechnet aus dem Schlüssel direkt den Speicherort des Werts. Statt zu suchen: direkt hinspringen.

position = hashfunktion(schlüssel)
wert = tabelle[position]

Hashfunktion:

Nimmt beliebig große Eingaben (z. B. Strings) und gibt eine Zahl (den Index) zurück.
Anforderungen: schnell berechenbar, gleichmäßige Verteilung, deterministisch (gleicher Input → gleicher Output).
Beispiel: hash("name") = (ord('n') + ord('a') + ord('m') + ord('e')) % tabellengröße.

Kollisionsauflösung: Wenn zwei Schlüssel dieselbe Position ergeben:

Chaining: Jede Position enthält eine verkettete Liste. Kollidierende Elemente kommen in die Liste.
Open Addressing: Suche die nächste freie Position.

Eigenschaften:

Einfügen, Suchen, Löschen: O(1) im Durchschnitt.
Worst Case (viele Kollisionen): O(n) — kann passieren bei schlechter Hashfunktion oder zu voller Tabelle.
Keine definierte Reihenfolge der Elemente.
Kein „nächstgrößeres Element” findbar — dafür besser Bäume.

Wann sinnvoll? Immer, wenn schnelles Nachschlagen per Schlüssel wichtiger ist als Reihenfolge. Wörterbücher, Caches, Datenbank-Lookups, Duplikat-Erkennung.

Datenbankindex

In einer Datenbank mit Millionen von Zeilen würde eine lineare Suche für jede Abfrage viel zu langsam sein. Deshalb gibt es Indizes.

Ein Index ist eine separate Datenstruktur (meistens ein B-Baum — eine ausgewogene Baumstruktur), die für eine Spalte (z. B. „Nachname”) vorberechnet, wo welcher Wert zu finden ist. Anstatt alle Zeilen zu durchsuchen, fragt die Datenbank den Index — und findet den Eintrag in O(log n).

Das ist genau das Prinzip des Telefonbuchs: Es ist alphabetisch sortiert, damit du nicht jede Seite lesen musst.

Nachteil: Indizes brauchen Speicher und verlangsamen das Einfügen/Aktualisieren (der Index muss mitgepflegt werden). Deshalb legt man nur für häufig gesuchte Spalten Indizes an.

Vergleich der drei Verfahren

Verfahren	Voraussetzung	Best Case	Worst Case	Anwendung
Lineare Suche	keine	O(1)	O(n)	kleine/unsortierte Daten
Binäre Suche	sortiert	O(1)	O(log n)	große sortierte Arrays
Hashing	Hashfunktion	O(1)	O(n)	schnelle Key-Lookups

Konkret: 1 Million Elemente

Lineare Suche: im Schnitt 500.000 Vergleiche
Binäre Suche: maximal 20 Vergleiche
Hashing: ~1 Vergleich (im Durchschnitt)

Beispiel aus dem Alltag

Telefonbuch: Ein altes gedrucktes Telefonbuch ist alphabetisch sortiert — du kannst binäre Suche anwenden (aufschlagen in der Mitte, dann links oder rechts). Ein zufällig angeordnetes Telefonbuch würde lineare Suche erfordern — unpraktisch.

Google: Google durchsucht nicht bei jeder Anfrage alle Seiten linear. Stattdessen gibt es vorberechnete Indizes (umgekehrte Indizes: Wort → Liste der Seiten, die es enthalten). Deine Anfrage wird gegen diese Indizes abgeglichen — im Wesentlichen ein Hash-Lookup kombiniert mit Ranking-Algorithmen.

Wörterbuch in deiner Programmiersprache: dict["name"] in Python, map["name"] in JavaScript — das ist eine HashMap-Suche. Direkte O(1)-Abfrage. Das ist der Grund, warum Maps für Lookups bevorzugt werden.

Anwendung

Du hast eine sortierte Liste von 128 Städten und willst wissen, ob „München” darin vorkommt.

Wie viele Schritte braucht lineare Suche im Worst Case?
Wie viele Schritte braucht binäre Suche maximal? (Tipp: log₂(128) = ?)
Wenn du dieselbe Abfrage für dieselbe Liste täglich tausendmal ausführst — wie würdest du die Suche optimieren?
Warum funktioniert binäre Suche nicht auf einer verketteten Liste?

Typische Fehler

Binäre Suche auf unsortierte Daten: Dann liefert sie falsche Ergebnisse. Vorbedingung zwingend prüfen.

Hashing = immer O(1) verwechseln: O(1) gilt nur im Durchschnitt. Bei vielen Kollisionen oder ungünstiger Hashfunktion sinkt die Performance. Gute Hashfunktionen und ausreichend Speicher sind Voraussetzung.

Index = Beschleunigung überall: Datenbankindizes beschleunigen Lesezugriffe, aber verlangsamen Schreibzugriffe (da der Index aktualisiert werden muss). Zu viele Indizes verringern die Write-Performance.

Suche und Sortieren verwechseln: Binäre Suche setzt voraus, dass die Daten schon sortiert sind. Das Sortieren selbst kostet O(n log n). Wenn du einmal sortierst und viele Male suchst, lohnt sich das. Wenn du nur einmal suchst, lohnt sich das Sortieren nicht.

Zusammenfassung

Lineare Suche: einfach, keine Vorbedingungen, aber O(n) — unpraktisch für große Daten
Binäre Suche: O(log n) — aber nur auf sortierten Daten; halbiert mit jedem Schritt den Suchraum
Hashing: O(1) im Durchschnitt durch direkte Adressierung per Hashfunktion; Kollisionen müssen aufgelöst werden
Bei 1 Million Elementen: lineare Suche ~500.000 Schritte, binäre Suche ~20, Hashing ~1
Datenbankindizes nutzen Baumstrukturen (B-Bäume), um Abfragen von O(n) auf O(log n) zu reduzieren
Die Wahl des Suchalgorithmus hängt davon ab, ob Daten sortiert sind, wie oft gesucht wird und ob Reihenfolge relevant ist

Quiz

Frage 1: Warum ist binäre Suche so viel schneller als lineare Suche — und was ist die Voraussetzung?

Frage 2: Was macht eine gute Hashfunktion aus?

Frage 3: Warum funktioniert binäre Suche nicht auf einer verketteten Liste?

Frage 4: Warum haben Datenbanken Indizes — und was ist der Nachteil?