Suchalgorithmen O(log n) vs O(n) in Python

Suchalgorithmen im Vergleich: O(n) vs. O(log n) für Entwickler

Bei Arrays mit Millionen von Elementen benötigt die lineare Suche bis zu 10 Millionen Operationen – während die binäre Suche bereits nach nur 24 Vergleichen abgeschlossen ist. Wir analysieren vier Suchalgorithmen in Python: Zeitkomplexität, praktische Kompromisse und Entscheidungshilfen für den Einsatz im echten Betrieb. Dazu gehören overflow-sichere Implementierungen, lower_bound/upper_bound sowie Beispiele, die direkt auf LeetCode einsetzbar sind.

Das Suchproblem: Gegeben eine Sammlung arr, finde den Index von target oder gib -1 zurück. Die Sammlung kann sortiert oder unsortiert sein, statisch oder dynamisch. Typische Anwendungsfälle sind die SKU-Suche im E-Commerce (Millionen von Artikeln) oder die Validierung von Transaktions-IDs im Finanzsektor.

Lineare Suche für unsortierte Daten

Funktioniert mit jeder Sammlung. Prüft die Elemente nacheinander.

Implementierung:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Komplexität:

• Zeit: O(n) im schlechtesten und durchschnittlichen Fall, O(1) im besten Fall.
• Speicher: O(1).

Binäre Suche und ihre Varianten

Setzt ein sortiertes Array voraus. Halbiert das Suchintervall wiederholt.

Iterative Implementierung: Verwende mid = left + (right - left) // 2, um Integer-Überläufe zu vermeiden (kritisch in C++/Java; in Python sicher, aber idiomatisch und robust).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Beispiel
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5))  # 3
print(lower_bound(sorted_arr, 3))     # 1
print(upper_bound(sorted_arr, 3))     # 3

Komplexität: O(log n) Zeit, O(1) Speicher.

lower_bound liefert die linkeste Einfügeposition für target; upper_bound die rechteste. Unverzichtbar beim Umgang mit Duplikaten und bei LeetCode-Aufgaben wie „Erstes und letztes Vorkommen eines Elements in einem sortierten Array“.

Exponentielle Suche für Streaming-Daten oder unbekannte Größe

Ideal für sortierte Arrays unbekannter Länge – oder wenn target wahrscheinlich nahe am Anfang liegt. Zuerst wird ein Begrenzungsintervall durch exponentielles Wachstum bestimmt, dann folgt eine binäre Suche.

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Beispiel
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456))  # 123456

Komplexität: O(log i), wobei i der Index des Ziels ist; im schlechtesten Fall O(log n); Speicher O(1).

Hashbasierte Suche für dynamische Sammlungen

Durchschnittlich O(1)-Zugriff mittels Hash-Tabellen (set/dict in Python).

def hash_search_set(arr, target):
    s = set(arr)
    return target in s

def hash_search_dict(pairs, key):
    d = dict(pairs)
    return d.get(key)

# Beispiel
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30))  # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b"))  # 2

Komplexität: O(1) im Durchschnitt, O(n) im schlechtesten Fall (bei Hash-Kollisionen), Speicher O(n).

Entscheidungshilfe für die Algorithmuswahl

• Unsortiertes Array: Lineare Suche bei N < 100 oder seltenen Abfragen.
• Sortierte & statische Daten: Binäre Suche.
• Dynamische Daten mit häufigen Einfügungen: Hash-Tabelle (Reihenfolge spielt keine Rolle).
• Streaming-Daten oder unbekannte Größe: Exponentielle Suche.

| Algorithmus | Durchschn. Zeit | Schlechtester Fall | Speicher | Voraussetzungen |

|-------------|----------------|----------------------|----------|------------------|

| Linear | O(n) | O(n) | O(1) | Beliebig |

| Binär | O(log n) | O(log n) | O(1) | Sortiert |

| Exponentiell | O(log i) | O(log n) | O(1) | Sortiert |

| Hash | O(1) | O(n) | O(n) | Hashbare Schlüssel |

Wichtigste Erkenntnisse

• Bei 10 Millionen Elementen benötigt die binäre Suche etwa 24 Vergleiche – im Gegensatz zu 10 Millionen bei der linearen Suche.
• Verwende immer die overflow-sichere Berechnung von mid in der binären Suche – auch in Python ist dies eine robuste Gewohnheit.
• Hash-Tabellen tauschen Speicher (O(n)) gegen extrem schnelle Durchschnitts-Zugriffszeiten (O(1)).
• lower_bound und upper_bound sind unverzichtbar für den Umgang mit Duplikaten und Einfügelogik.
• Die exponentielle Suche überzeugt besonders, wenn Zielwerte am Anfang sehr großer sortierter Arrays konzentriert sind.

— Editorial Team