Such-Algorithmen

“Wo ist X in der Datenmenge?” - die wohl haeufigste Frage in der Programmierung. Es gibt mehrere Antworten, je nach Datenstruktur.

Lineare Suche - O(n)

Geh durch die Liste, pruefe jedes Element:

def linear_search(liste, ziel):
    for i, wert in enumerate(liste):
        if wert == ziel:
            return i
    return -1

print(linear_search([10, 20, 30, 40], 30))  # 2
print(linear_search([10, 20, 30, 40], 99))  # -1

Wann nutzen?

• Unsortierte Listen
• Kleine Listen - Aufwand lohnt sich nicht
• Wenn du die Daten ohnehin einmalig durchlaeufst

Python-Builtins

liste.index(30)    # Linear Search, wirft Exception wenn nicht gefunden
30 in liste        # Linear Search, True/False

Komplexitaet

• Best: O(1) (gleich erstes Element)
• Average: O(n/2) = O(n)
• Worst: O(n)

Binaere Suche - O(log n)

Bei sortierten Listen viel schneller:

def binary_search(sortierte_liste, ziel):
    links, rechts = 0, len(sortierte_liste) - 1

    while links <= rechts:
        mitte = (links + rechts) // 2
        if sortierte_liste[mitte] == ziel:
            return mitte
        if sortierte_liste[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1

    return -1

Bei jeder Iteration halbiert sich der Suchraum - bei 1 Million Elementen reichen ~20 Schritte.

Komplexitaet

• Alles: O(log n)

Aber Voraussetzung: sortierte Liste.

Python-Alternative: bisect

import bisect

sortiert = [1, 3, 5, 7, 9, 11]

idx = bisect.bisect_left(sortiert, 5)
# 2 - Position, wo 5 eingefuegt werden wuerde (hier: existiert schon)

# Praktisch: Einfuegen in sortierte Liste
bisect.insort(sortiert, 6)
print(sortiert)  # [1, 3, 5, 6, 7, 9, 11]

bisect nutzt binaere Suche - perfekt fuer sortierte Listen, in die du laufend einfuegst.

Rekursive Variante

def binary_search_rec(arr, ziel, links=0, rechts=None):
    if rechts is None:
        rechts = len(arr) - 1
    if links > rechts:
        return -1

    mitte = (links + rechts) // 2

    if arr[mitte] == ziel:
        return mitte
    if arr[mitte] < ziel:
        return binary_search_rec(arr, ziel, mitte + 1, rechts)
    return binary_search_rec(arr, ziel, links, mitte - 1)

Schoen elegant - in der Praxis nutzt man meist die iterative Version (weniger Stack-Aufwand).

Hash-Lookup - O(1)

Der schnellste Weg, wenn die Daten in einem Dict/Set sind:

liste = [10, 20, 30, 40]
set_version = set(liste)

# Enthalten?
30 in set_version    # O(1)
99 in set_version    # O(1)

Das Konvertieren kostet O(n), aber dann sind alle Lookups O(1).

Typisches Pattern

def gemeinsame_elemente(a, b):
    set_a = set(a)
    return [x for x in b if x in set_a]

• Ohne Set: O(n * m) (Suche jedes Element)
• Mit Set: O(n + m)

Die Wahl: Wann was?

Situation	Wahl
Unsortierte Liste, einmal suchen	Linear Search
Sortierte Liste	Binary Search
Haeufige Lookups auf viele Daten	Hash (Set/Dict)
Unbekannt, welcher Index	Linear
Datenbank-Feld	Index (B-Tree, Hash)
Prefix-Suche (Autocomplete)	Trie
Substring in String	KMP, Boyer-Moore

Spezielle Varianten

Binary Search - Leftmost / Rightmost

Was, wenn es mehrere Elemente mit dem gleichen Wert gibt? Manchmal willst du das erste oder letzte:

def leftmost(arr, ziel):
    links, rechts = 0, len(arr)
    while links < rechts:
        mitte = (links + rechts) // 2
        if arr[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte
    return links if links < len(arr) and arr[links] == ziel else -1

bisect.bisect_left und bisect.bisect_right sind die fertigen Varianten.

Exponentielle Suche

Wenn du nicht weisst, wie gross die Liste ist (z.B. Streams):

1. Fange bei Index 1 an, verdopple, bis der Wert zu gross
2. Binary Search in dem gefundenen Bereich

Nuetzlich fuer “unbounded” Daten. Komplexitaet: O(log i), wo i = Position des Ziels.

Interpolation Search

Fuer gleichmaessig verteilte Daten (z.B. Telefonbuch):

def interpolation_search(arr, ziel):
    low, high = 0, len(arr) - 1
    while low <= high and arr[low] <= ziel <= arr[high]:
        if low == high:
            return low if arr[low] == ziel else -1

        # Geschaetzte Position
        pos = low + ((ziel - arr[low]) * (high - low)) // (arr[high] - arr[low])

        if arr[pos] == ziel:
            return pos
        if arr[pos] < ziel:
            low = pos + 1
        else:
            high = pos - 1
    return -1

Kann O(log log n) erreichen - aber nur bei gut verteilten Daten. Bei schlechten Daten: O(n).

Suche in Strings

Naive Substring-Suche

def naive_find(text, pattern):
    for i in range(len(text) - len(pattern) + 1):
        if text[i:i + len(pattern)] == pattern:
            return i
    return -1

O(n*m) - OK fuer kurze Strings.

Python: str.find / str.index / in

Python’s in-Operator fuer Strings ist sehr optimiert:

"lorem ipsum".find("ipsum")   # 6
"ipsum" in "lorem ipsum"       # True

Intern wird ein schneller Algorithmus wie Boyer-Moore-Horspool oder Two-Way genutzt.

Regex

Fuer Pattern-Matching:

import re

if re.search(r"\d{3}-\d{4}", text):
    print("Telefonnummer gefunden")

Suche in Baeumen und Graphen

Hatten wir im vorherigen Kapitel:

• BFS - level-by-level, findet kuerzeste ungewichtete Pfade
• DFS - tief, findet Pfade, Zyklen
• Dijkstra - gewichtete kuerzeste Pfade
• A* - gewichtete Pfade mit Heuristik (GPS, Games)

Fuzzy Search / Approximate Matching

Wenn der User “Paris” tippt und du “Parsis” findest:

• Levenshtein Distance misst “Aehnlichkeit” zwischen Strings
• Trigrams / Shingles fuer schnelle approximative Suche
• Libraries: rapidfuzz (Python), fuse.js (JavaScript)

from rapidfuzz import process

kandidaten = ["Paris", "Parsons", "Parma", "Peru"]
result = process.extractOne("Pris", kandidaten)
print(result)  # ('Paris', 88.9, 0)

Volltextsuche - Elasticsearch & Co.

Fuer echte Volltextsuche (Google-like) nutzt man spezielle Tools:

• Elasticsearch / OpenSearch
• Meilisearch - einfacher, sehr schnell
• Typesense
• PostgreSQL Full Text Search
• SQLite FTS5

Sie bauen Inverted Indexes und unterstuetzen Tokenization, Stemming, Ranking.

Ein kleines Beispiel

Finde Element mit Hilfsdaten in sortierter Liste:

import bisect

class Inventar:
    def __init__(self):
        self.items = []          # sortiert nach Preis

    def hinzufuegen(self, produkt, preis):
        bisect.insort(self.items, (preis, produkt))

    def finde_billigste_N(self, n):
        return self.items[:n]

    def finde_in_range(self, min_p, max_p):
        low = bisect.bisect_left(self.items, (min_p,))
        high = bisect.bisect_right(self.items, (max_p + 1,))
        return self.items[low:high]

inv = Inventar()
inv.hinzufuegen("Buch", 19.99)
inv.hinzufuegen("Kaffee", 3.50)
inv.hinzufuegen("Tasse", 8.00)

print(inv.finde_billigste_N(2))
print(inv.finde_in_range(5, 20))

bisect gibt uns O(log n) fuer Einfuegen und Bereichssuche.

Performance-Tipps

Frueh abbrechen

# Lang
for x in liste:
    if x == ziel:
        gefunden = True
        break

any() / all() shortcircuiten

if any(x > 100 for x in werte):
    # ...

Set statt Liste

Immer dann, wenn du haeufig “enthaelt X?” pruefst.

Vermeidung von list.index in Schleifen

# Schlecht: O(n²)
for wert in ziele:
    idx = liste.index(wert)

# Besser: Index-Map aufbauen
index_map = {w: i for i, w in enumerate(liste)}
for wert in ziele:
    idx = index_map.get(wert)

Zusammenfassung

• Linear Search O(n) - fuer unsortierte Listen
• Binary Search O(log n) - fuer sortierte Listen, via bisect in Python
• Hash Lookup O(1) - fuer Sets/Dicts
• in Operator ist linear auf Liste, O(1) auf Set
• BFS/DFS fuer Graphen
• Fuzzy Search mit Libraries wie rapidfuzz
• Volltextsuche ueber Tools wie Meilisearch/Elasticsearch

Damit hast du den Algorithmen-Werkzeugkasten zusammen. Im weiteren Kurs vertiefen wir Dynamic Programming, Greedy-Algorithmen und Complexity Theory.