Hoe wordt de tijdcomplexiteit van het binaire zoekalgoritme bepaald?

De tijdcomplexiteit van het binaire zoekalgoritme wordt gedefinieerd als O(log n), waarbij n het aantal elementen in de gesorteerde array is. Dit komt doordat het algoritme bij elke stap het zoekgebied in tweeën deelt, waardoor het aantal te overwegen elementen wordt gehalveerd, totdat het gezochte element wordt gevonden of de afwezigheid ervan wordt bevestigd.

Voorbeeld 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 niet gevonden
}