Wie wird die zeitliche Komplexität des binären Suchalgorithmus bestimmt?

Die zeitliche Komplexität des binären Suchalgorithmus wird als O(log n) definiert, wobei n die Anzahl der Elemente im sortierten Array ist. Dies liegt daran, dass der Algorithmus bei jedem Schritt den Suchbereich halbiert, wodurch die Anzahl der betrachteten Elemente verdoppelt wird, bis das gesuchte Element gefunden wird oder seine Abwesenheit bestätigt ist.

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
}