Como funciona a pesquisa binária numa lista ordenada?

A pesquisa binária é um algoritmo para encontrar um elemento numa lista ordenada com complexidade logarítmica O(log n). Funciona segundo o princípio de "divide e conquistar":

1. Determina-se o elemento médio da lista.
2. Se o elemento procurado for igual ao médio, a pesquisa termina.
3. Se o elemento procurado for menor que o médio, a pesquisa continua na metade esquerda da lista.
4. Se for maior, na metade direita.

O processo repete-se de forma recursiva ou iterativa até que o elemento seja encontrado ou o intervalo de pesquisa se esgote.

Exemplo em 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 não encontrado
}