Wie ist die Komplexität der binären Suche und warum?

Die Komplexität der binären Suche ist O(log n), wobei n die Anzahl der Elemente im sortierten Array ist. Dies liegt daran, dass der Algorithmus bei jedem Schritt den Suchbereich halbiert und die Hälfte der Elemente ausschließt, die den gesuchten Wert nicht enthalten können. Somit wächst die Anzahl der Operationen logarithmisch mit der Größe der Eingabedaten.

Beispiel in Go:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // Element nicht gefunden
}