¿Cuál es la complejidad de la búsqueda binaria y por qué?

La complejidad de la búsqueda binaria es O(log n), donde n es la cantidad de elementos en el array ordenado. Esto se debe a que en cada paso el algoritmo divide el área de búsqueda por la mitad, descartando la mitad de los elementos que no pueden contener el valor buscado. De esta manera, la cantidad de operaciones crece logarítmicamente con respecto al tamaño de los datos de entrada.

Ejemplo en 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 // elemento no encontrado
}