Wat is de complexiteit van binaire zoekopdrachten en waarom?

De complexiteit van binaire zoekopdrachten is 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, waarbij de helft van de elementen wordt uitgesloten die de gezochte waarde niet kunnen bevatten. Op deze manier groeit het aantal bewerkingen logaritmisch met de grootte van de invoergegevens.

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
}