Busca Binária

Conceito

Busca binária responde "onde está x?" descartando metade dos candidatos a cada comparação. Daí o log₂ n: com um milhão de elementos, 20 comparações.

A pré-condição é ordenação, e ela não é negociável. Sobre dados desordenados o algoritmo não fica lento — fica errado: ele descarta a metade que continha o alvo e responde "não existe". Falha silenciosa, sem erro.

O invariante que faz tudo funcionar: se x existe, ele está dentro de [lo, hi]. Cada iteração encolhe esse intervalo mantendo o invariante. Quando o intervalo esvazia, x não existe.

O bug de overflow. (lo + hi) / 2 estoura quando lo + hi passa do máximo do tipo. Isso não é hipotético: esteve no JDK por nove anos e no livro Programming Pearls por duas décadas. A forma segura:

mid = lo + (hi - lo) / 2

O off-by-one, e como evitá-lo de vez. Existem dois estilos consistentes, e o bug nasce de misturá-los:

Escolha um e nunca misture. O semiaberto tende a dar menos erro porque hi é sempre "um além do válido", que é a mesma convenção de slice.

A generalização que vale mais que a busca em si: lower_bound. Em vez de parar quando encontra, continue encolhendo. Isso responde não só "onde está", mas:

• primeira ocorrência de um valor repetido
• primeiro elemento ≥ x
• quantos elementos são menores que x
• onde inserir mantendo a ordem

E a aplicação mais poderosa: busca binária sobre a resposta. Se existe um predicado monotônico (se vale para k, vale para todo k' > k), você pode buscar binariamente o menor k que satisfaz — mesmo sem array nenhum. "Qual a menor capacidade de navio que entrega em D dias?" é busca binária.

Em Go

A stdlib te dá exatamente a versão útil:

i, achou := slices.BinarySearch(s, v)

Quando achou é false, i é onde inserir para manter a ordem — ou seja, é lower_bound. Isso resolve inserção ordenada e contagem de menores sem escrever nada:

s = slices.Insert(s, i, v) // insere na posição correta

slices.BinarySearchFunc para comparadores próprios (structs, ordem descendente).

E a forma mais geral, que muita gente não conhece: sort.Search faz busca binária sobre um predicado, sem exigir slice nenhum:

// menor i em [0, n) onde f(i) é true
i := sort.Search(n, func(i int) bool { return caroSuficiente(i) })

É a "busca binária sobre a resposta" pronta na biblioteca padrão.

Detalhe bonito: o próprio Go evita o overflow de um jeito diferente do usual — h := int(uint(i+j) >> 1). A soma em uint não estoura para índices válidos, e o shift divide por dois. Vale ler sort.Search uma vez.

Respostas às perguntas-guia

1. Qual a pré-condição obrigatória, e o que acontece se ela não valer?

Conceito: ordenação. Sem ela o resultado é incorreto, não lento — o descarte elimina a metade errada.

Em Go: slices.BinarySearch sobre slice desordenado devolve resultado inválido sem panic e sem aviso — e, pior, às vezes acerta por acidente (quando o alvo cai no primeiro mid testado). Um teste que só exercita o caso sortudo passa. Não há verificação na função porque verificar custaria O(n) e destruiria o propósito.

2. Por que (lo + hi) / 2 pode estourar, e qual a forma segura?

Conceito: lo + hi pode passar do máximo do tipo. Seguro: lo + (hi-lo)/2.

Em Go: int é 64 bits em plataformas modernas, então o overflow é praticamente inalcançável na prática — mas o int de Go não tem tamanho garantido pela especificação, e o hábito é o que te protege quando você escrever em outra linguagem. A stdlib usa int(uint(i+j) >> 1).

3. Onde fica o off-by-one: lo <= hi ou lo < hi? Por quê?

Conceito: depende do intervalo. Fechado [lo,hi] pede lo <= hi; semiaberto [lo,hi) pede lo < hi. O bug é misturar as convenções.

Em Go: a stdlib usa semiaberto, o que combina com a semântica de slice (s[a:b] exclui b). Seguir a mesma convenção no seu código elimina a troca mental.

4. Como usá-la para achar a primeira ocorrência, não qualquer uma?

Conceito: não pare ao encontrar — registre e continue encolhendo hi. É o lower_bound.

Em Go: já está feito: slices.BinarySearch devolve a primeira posição possível. Para a última ocorrência, busque o lower_bound de v+1 e subtraia 1 — o idioma que resolve "quantos iguais a v" em duas buscas.

Trade-offs

Do conceito:

• O(log n) em troca de manter os dados ordenados. Se as escritas são frequentes, o custo de manter a ordem pode superar o ganho da busca — aí 6. Hash Map é melhor.
• Busca binária compra ordem e faixa; hash compra O(1) e perde as duas.
• lower_bound é estritamente mais útil que "achou/não achou" e custa o mesmo.

Em Go:

• slices.BinarySearch (generics) contra sort.Search (predicado): a primeira é mais direta, a segunda é mais geral. Nenhuma usa reflexão.
• Manter slice ordenado + BinarySearch é uma alternativa real a árvore (2. Árvore de Busca Binária): busca O(log n), inserção O(n) mas com memmove e localidade perfeita — vence árvore de ponteiros até alguns milhares de elementos.

Exemplo prático

package main

import (
	"fmt"
	"slices"
	"sort"
)

// Estilo semiaberto [lo, hi) — a mesma convenção dos slices de Go
func busca(s []int, v int) (int, bool) {
	lo, hi := 0, len(s)
	for lo < hi {
		mid := lo + (hi-lo)/2 // nunca (lo+hi)/2
		switch {
		case s[mid] == v:
			return mid, true
		case s[mid] < v:
			lo = mid + 1
		default:
			hi = mid
		}
	}
	return lo, false // lo é onde INSERIR
}

// lower_bound: primeira posição onde s[i] >= v
func lowerBound(s []int, v int) int {
	lo, hi := 0, len(s)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if s[mid] < v {
			lo = mid + 1
		} else {
			hi = mid // NÃO para ao achar: continua encolhendo
		}
	}
	return lo
}

func main() {
	s := []int{1, 3, 3, 3, 5, 7, 9}

	i, ok := busca(s, 5)
	fmt.Println("busca(5):", i, ok)
	i, ok = busca(s, 6)
	fmt.Println("busca(6):", i, ok, "<- onde inserir o 6")

	// primeira e última ocorrência do 3, em duas buscas
	primeira := lowerBound(s, 3)
	ultima := lowerBound(s, 4) - 1
	fmt.Printf("3 ocupa [%d..%d] = %d ocorrências\n", primeira, ultima, ultima-primeira+1)

	// a stdlib já dá lower_bound
	j, achou := slices.BinarySearch(s, 6)
	fmt.Println("slices.BinarySearch(6):", j, achou)
	s2 := slices.Insert(slices.Clone(s), j, 6)
	fmt.Println("inserido na ordem:", s2)

	// sobre dados DESORDENADOS: erra silenciosamente — e às vezes ACERTA por acidente,
	// o que é pior, porque o bug passa em teste.
	ruim := []int{5, 1, 9, 3, 7}
	for _, v := range []int{9, 7} {
		k, achou := slices.BinarySearch(ruim, v)
		fmt.Printf("desordenado: %d está no índice %d | BinarySearch diz i=%d achou=%v\n",
			v, slices.Index(ruim, v), k, achou)
	}

	// busca binária sobre a RESPOSTA: menor k tal que k*k >= 1000
	k := sort.Search(1000, func(k int) bool { return k*k >= 1000 })
	fmt.Printf("menor k com k²>=1000: %d (%d²=%d)\n", k, k, k*k)

	// mesma ideia, problema real: menor capacidade que entrega em 3 dias
	pesos := []int{3, 2, 2, 4, 1, 4}
	capac := sort.Search(20, func(c int) bool {
		if c < slices.Max(pesos) { return false }
		dias, carga := 1, 0
		for _, p := range pesos {
			if carga+p > c { dias++; carga = 0 }
			carga += p
		}
		return dias <= 3
	})
	fmt.Println("menor capacidade para 3 dias:", capac)
}

Relacionado

• 2. Árvore de Busca Binária — semana 3, o mesmo descarte sobre estrutura ligada
• 4. Dois Ponteiros — o outro padrão que exige ordenação
• 6. Hash Map — semana 2, O(1) sem ordem contra O(log n) com ordem
• 5. Índices — semana 9, a B-tree é busca binária em disco

---

Parte de Semana 04 - Algoritmos Essenciais · 00 - MOC Fundamentos de Programação