What is the complexity of binary search and why?

The complexity of binary search is O(log n), where n is the number of elements in the sorted array. This is because at each step, the algorithm divides the search area in half, discarding the half of elements that cannot contain the sought value. Thus, the number of operations grows logarithmically with the size of the input data.

Example 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 not found
}