Armadilhas da busca binária: overflow no ponto médio e limites com erro de uma unidade

O que é

A busca binária encontra uma posição em dados ordenados dividindo ao meio, repetidamente, o intervalo de candidatos. Três bugs se repetem. Primeiro, o overflow no ponto médio: o post do Google Research citado descreve como (low + high) / 2 falha no binarySearch do JDK quando a soma ultrapassa o valor máximo de int, e indica low + ((high - low) / 2) ou (low + high) >>> 1 como correções. Segundo, a convenção de limites: se high é inclusivo ou exclusivo determina a condição do laço e as atualizações; misturar convenções gera laços infinitos ou um elemento ignorado. Terceiro, os duplicados: o bisect do Python documenta bisect_left (ponto de inserção antes das entradas iguais) e bisect_right (depois delas), que é a diferença entre "primeira ocorrência" e "posição após a última ocorrência". O sort.Search do Go evita a maior parte disso ao pedir o menor índice em [0, n) a partir do qual um predicado monótono passa a ser verdadeiro.

Por que importa

A rotina aparece em cursores de paginação, consultas em séries temporais, verificações de faixas de versões, buscas sobre builds no estilo git bisect e em muitas tarefas do tipo "encontre o primeiro que falha". Um limite errado passa despercebido: os resultados ficam errados por uma unidade apenas para algumas entradas, tipicamente o primeiro ou o último elemento.

Como aplicar

• Prefira a função da biblioteca (bisect, sort.Search, Arrays.binarySearch); escreva a sua própria apenas quando o predicado não for uma consulta em array.
• Use a forma com predicado: encontre o primeiro índice em que pred(i) é verdadeiro, exigindo que pred seja falso e depois verdadeiro ao longo do intervalo. Limite inferior, limite superior e "primeira versão que falha" são todos instâncias disso.
• Use um intervalo semiaberto: lo, hi = 0, n; enquanto lo < hi: mid = lo + (hi - lo) // 2; se pred(mid): hi = mid, senão lo = mid + 1; retorne lo. O + 1 no ramo else garante que o laço avance.
• Teste os extremos: entrada vazia, um único elemento, alvo abaixo do primeiro e acima do último, todos os elementos iguais, alvo nos índices 0 e n-1.
• Verifique se os dados estão ordenados segundo a mesma comparação usada na busca (bisect com key= deve corresponder à chave da ordenação).

Armadilhas

Inteiros em Python não estouram, mas os bugs de limites continuam. Uma busca sobre floats quebra na presença de NaN, porque as comparações deixam de formar uma ordenação. Dados ordenados com collation de locale e pesquisados byte a byte não estão ordenados para a busca. bisect_left retorna um ponto de inserção para valores ausentes, não -1: verifique i < len(a) and a[i] == x. A busca binária em uma lista encadeada é linear, porque o acesso por índice é linear.