Welcher Algorithmus hat eine logarithmische Komplexität O(log n)?

Der binäre Suchalgorithmus (oder dichotome Suche) hat eine logarithmische Laufzeitkomplexität O(log n).

Funktionsprinzip der binären Suche:

1. Erfordert ein sortiertes Array (oder eine Liste).
2. Vergleicht in jedem Schritt das gesuchte Element mit dem Element in der Mitte des aktuellen Suchbereichs.
3. Wenn die Elemente übereinstimmen, ist die Suche beendet.
4. Wenn das gesuchte Element kleiner als das mittlere ist, wird die Suche im linken Bereich fortgesetzt.
5. Wenn das gesuchte Element größer als das mittlere ist, wird die Suche im rechten Bereich fortgesetzt.
6. Der Suchbereich halbiert sich bei jedem Schritt.

Beispiel für eine Implementierung in Python:

# Funktion für binäre Suche
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Element gefunden, gibt den Index zurück
        elif mid_val < target:
            low = mid + 1  # Ignoriert die linke Hälfte
        else:
            high = mid - 1  # Ignoriert die rechte Hälfte

    return -1  # Element nicht gefunden

# Beispiel für die Verwendung
# sortierte_liste = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# zielwert = 23
# ergebnis = binary_search(sortierte_liste, zielwert)
# if ergebnis != -1:
#     print(f"Element gefunden bei Index: {ergebnis}")
# else:
#     print("Element nicht gefunden")

Die logarithmische Komplexität ergibt sich daraus, dass die Anzahl der Operationen proportional zum Logarithmus der Eingabedaten (n) ist, da bei jedem Schritt der Suchraum halbiert wird.