Wie funktioniert der binäre Suchalgorithmus?

Die binäre Suche funktioniert, indem sie ein sortiertes Array analysiert und das Suchintervall wiederholt in der Mitte teilt.

1. Initialisierung: Es werden die linke und rechte Grenze des Suchintervalls festgelegt (normalerweise Anfang und Ende des Arrays).
2. Vergleich: Der Index der Mitte des Intervalls wird berechnet. Der Wert an diesem Index wird mit dem gesuchten Element verglichen.
3. Verkleinerung des Intervalls:
   • Wenn der Wert in der Mitte mit dem gesuchten übereinstimmt, wurde das Element gefunden.
   • Wenn der Wert in der Mitte größer als das Gesuchte ist, wird die Suche im linken Halbintervall fortgesetzt. Die rechte Grenze verschiebt sich auf Mitte - 1.
   • Wenn der Wert in der Mitte kleiner als das Gesuchte ist, wird die Suche im rechten Halbintervall fortgesetzt. Die linke Grenze verschiebt sich auf Mitte + 1.
4. Wiederholung: Die Schritte 2 und 3 werden wiederholt, bis das Element gefunden wird oder das Suchintervall leer ist.

Die Komplexität des Algorithmus ist O(log n), was deutlich effizienter ist als lineare Suche bei großen Arrays.

Beispiel für eine Implementierung in Python:

def binary_search(arr, target):
    """
    Implementierung der binären Suche.
    Nimmt ein sortiertes Array und den gesuchten Wert.
    Gibt den Index des Elements oder -1 zurück, wenn es nicht gefunden wird.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Berechnung des Mittelindex
        mid_val = arr[mid]      # Wert in der Mitte

        if mid_val == target:
            return mid  # Element gefunden
        elif mid_val < target:
            left = mid + 1  # Gesuchter Wert ist größer, Suche rechts
        else: # mid_val > target
            right = mid - 1 # Gesuchter Wert ist kleiner, Suche links

    return -1 # Element nicht gefunden