Erklären Sie das Funktionsprinzip des binären Suchalgorithmus und seine wichtigsten Schritte.

Die binäre Suche ist ein effizienter Algorithmus zur Suche eines Elements in einem sortierten Array. Ihr Prinzip besteht darin, den Suchbereich wiederholt in zwei Hälften zu teilen und den gesuchten Wert mit dem Element in der Mitte zu vergleichen.

Hauptschritte:

1. Bestimmen Sie die Anfangsgrenzen der Suche: linke und rechte Indizes.
2. Finden Sie den mittleren Index: mid = (left + right) // 2.
3. Vergleichen Sie den gesuchten Wert mit dem Element bei mid.
   • Wenn sie gleich sind, geben Sie den Index mid zurück.
   • Wenn der gesuchte Wert kleiner ist, verschieben Sie die rechte Grenze auf mid - 1.
   • Wenn er größer ist, verschieben Sie die linke Grenze auf mid + 1.
4. Wiederholen Sie die Schritte 2-3, bis die linke Grenze die rechte übersteigt.

Wenn das Element nicht gefunden wird, geben Sie beispielsweise -1 zurück.

Beispiel in Python:

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